【NC14399】素数判断

题目

素数判断

分解质因数

思路

题目很直接，给你一个数，判断其是不是素数，如果是，输出一句话和它本身，如果不是，输出一句话和它的质因数，需要注意的是质因数要从小到大输出。

我们知道，一个素数的质因数就是它本身，所以抛开素数判断，直接对一个数分解质因数就行了。

怎么对一个数分解质因数呢?

可以使用试除法来实现。对于一个大于 1 1 1 的正整数 n n n，如果 n n n 能被 [ 2 , s q r t ( n ) ] [2, sqrt(n)] [2,sqrt(n)] 范围内的任何整数整除，则将因子加入列表，直到 n = 1 n=1 n=1 或者因子的枚举值超出上述范围为止。

然后可以根据得到的质因数列表来判断一个数是不是素数

很直观，如果列表里面只有一个数，那么这个数肯定是素数，否则不是素数

需要注意的是以上的方法得到的质因数列表包含了重复的质因数，所以在输出的时候要加以判断。

代码

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

/**
 * @brief 分解质因数
 *
 * @param x 待分解的数
 * @return vector<int> 质因数列表
 */
vector<int> prime_factors(int x) {
    vector<int> res;
    int d = 2;
    while (x > 1) {
        while (x % d == 0) {
            res.emplace_back(d);
            x /= d;
        }
        d++;
        if (x > 1 && d * d > x) {
            res.emplace_back(x);
            break;
        }
    }
    return res;
}

int main(void) {
    int t = 0, x = 0, k = 0, i = 0;
    cin >> t;
    vector<int> tmp;
    while (t--) {
        cin >> x;
        tmp = std::move(prime_factors(x));
        cout << ((k = tmp.size()) == 1 ? "isprime" : "noprime") << endl;
        cout << tmp[0];
        for (i = 1; i < k; i++) {
            if (tmp[i] != tmp[i - 1]) {
                cout << " " << tmp[i];
            }
        }
        cout << endl;
    }
    return 0;
}