素数判断

题目

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

解题思路

使用筛法求素数会内存超限。所以，使用试除法求素数：令 i 的取值范围为 [2, sqrt(x)]，若 i 能整除 x，则 x 不是质数，记录因子。

C++代码

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int main(){
    int T;
    cin >> T;
    int x;
    while(T--){
        cin >> x;
        bool flag = true;
        vector<int> ans;
        int n = sqrt(x);
        for(int i=2; i<=n; ++i){
            if(x % i == 0){
                flag = false;
                ans.push_back(i);
                while(x % i == 0)
                    x /= i;
            }
            if(x == 1)
                break;
        }
        if(flag){
            cout << "isprime" << endl << x << endl;
        }
        else{
            cout << "noprime" << endl;
            for(int i=0; i<ans.size()-1; ++i){
                cout << ans[i] << " ";
            }
            cout << ans.back();
            if(x != 1)
                cout << " " << x;
            cout << endl;
        }
    }
    return 0;
}