题目描述

样例1

输入

3
2
9
10

输出

isprime
2
noprime
3
noprime
2 5

算法1

(快速判断快速求值)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) 
    {
        if (n <= 1) return false; // 0 和 1 不是素数  
        if (n <= 3) return true;  // 2 和 3 是素数  
        if (n % 2 == 0 || n % 3 == 0) return false; // 排除 2 和 3 的倍数  
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false; // 检查 i 和 i + 2  
            }
        }
        return true; // n 是素数  
}
vector<int> factor(int n)//取素因子
{
    vector<int>vk;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            vk.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) vk.push_back(n);
    return vk;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        if (isPrime(n))
        {
            cout << "isprime" << endl << n << endl;
        }
        else
        {
            cout << "noprime" << endl;
            vector<int>vk = factor(n);
            for (auto& v : vk)cout << v << ' ';
            cout<<endl;
        }
    }
    return 0;
}