给出一个数x，判断它是否为素数，并输出所有它的素因子

Question

给出一个数x，判断它是否为素数，并输出所有它的素因子
第1行输入组数T，代表有T组数据。
第2-T+1行每行输入一个数x表示对应询问。
数据保证：2≤x≤1e9
对于每组询问输出两行表示结果。
第1行，如果x是素数，输出“isprime”（不含双引号），否则输出“noprime”（不含双引号）。
第2行，输出x的素因子。
示例1
输入
3
2
9
10
输出
isprime
2
noprime
3
noprime
2 5

我写的代码提交总是超时， 我想的是创建两个函数一个是判断是否是素数，一个是分解成质因数，之后放在set里去重排序再输出出来，可是会超时，有哥帮忙看看如何改进一下吗。

#include<iostream>
#include<set>
using namespace std;
set<int> s;
bool prime(int n){
    bool yes=true;
      for(int i=2;i*i<=n;i++){
        if(n%i==0){
        yes=false;
    }
   }
   return yes;
}
void fjys(int n){
    for(int i=2;i<=n;i++){
            if(n%i==0){
               if(prime(i)){
                   s.insert(i);
               }
               else {
                   fjys(i);
               }
                          }
                 n/=i;                    
                }
            return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        s.clear();
        int n;
        cin>>n;
        if(prime(n)){
            cout<<"isprime"<<endl<<n<<endl;
        }
        else{
            cout<<"noprime"<<endl;
            for(int i=2;i<=n;i++){
            if(n%i==0){
                if(prime(i)){
                    s.insert(i);
                    n/=i;
                }
                else {
                    fjys(i);
                    n/=i;
                }
                    }                    
                        }
                for (auto it = s.begin(); it != s.end();it++)
            {
                     cout<<*it<<' ';
              }
            cout<<endl;    
        }
    }
    return 0;
}

Answer 1

嗯，我觉得主要还是计算它的质因子那里有点问题哈。在打印"noprime"下面那个for循环里，i最坏情况会枚举到根号n，而对于i，每次都会调用判定质数的函数，那个里面最坏情况会有根号i，这样总的复杂度可能会到n的3/4次幂，而这个题目我估计它的期望复杂度是根号n吧。

一般，想要计算n的所有质因子可以这么来哈

int n; cin>>n; // 待处理的正整数n
vector<int> pd; // 装填n的所有质因子
for(int i = 2; i * i <= n; i++){ // 从2开始
    if(n % i == 0){ // 如果能整除说明，此时i必定是质数，且是n的质因子。假如此时i不是质数，那么i必然包含某个质数x，因为n是i的倍数，而i又是x的倍数，那么n必然是x的倍数，那么在更早的时候必然已经遇到过x了，并且结合下面的while循环，x已经全部被除掉了，此时n不可能再是x的倍数了，出现矛盾
        pd.push_back(i); //装填质因子
        while(n % i == 0){ //把n所含的i全部除掉
              n = n / i; 
        }
    }
}
if(n > 1) { //小心边界情况，如果此时n还大于1，说明n也必然是质数，证明同上
   pd.push_back(n);
}
//最后通过检查pd是否为空即可判定n是否质数
if(pd.empty()){
   
} else {
    for(int i = 0; i < pd.size(); i++){
        cout<<pd[i]<<" ";
    }
}