题解 | #素数判断#

素数判断

#include <bits/stdc++.h>

using namespace std;

int n, T;

bool isprime(int n)//普通的判断素数
{
    bool f = true;
    for(int i = 2; i <= n / i; i ++)
        if(n % i == 0)
        {
            f = false;
            break;
        }
    return f;
}

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n;
        if(isprime(n))
        {
            cout << "isprime" << endl << n << endl;
        }
        else
        {
            cout << "noprime" << endl;
            for(int i = 2; i <= n / i; i ++)//分解质因数
            { 
                if(n % i == 0)
                {
                    cout << i << ' ';
                    while(n % i == 0) n /= i;
                }                
            }
            if(n > 1) cout << n << endl;
            else cout << endl;
        }
    }
    
    return 0;
}