题解 | 质数因子

#include <iostream>
#include<math.h>//用一下sqrt
using namespace std;

#define int long long  // 将 int 替换为 long long，n的最大值会爆int

const int N = 1e6 + 17;  // 根据需求调整大小
bool st[N];//用于检测是否为质数
int pri[N], idx;//用于存储质数
int cnt[N];//用于存储质数的个数比如180中2个2，那pri[1]=2,cnt[1]=2;

void get_pri(int n) {//先求质数
    for (int i = 2; i <= sqrt(n)+10; i++) {//用sqrt提高效率，就不全部遍历了。
        if (!st[i]) {
            pri[++idx] = i;
            int res = 0;
            while (n % i == 0) {//找该质数对应个数
                n /= i;
                res++;
            }
            cnt[idx] = res;
        }
        for (int j = 1; j <= idx && pri[j] <= n / i; j++) {
            st[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
        if (i * i > n) break;  // 提前退出循环
    }
    if (n > 1) {  // 如果 n 是质数
        pri[++idx] = n;
        cnt[idx] = 1;
    }
}

signed main() {  // 使用 signed 代替 int，因为 int 已被替换为 long long
    int n = 0;
    cin >> n;
    get_pri(n);

    for (int i = 1; i <= idx; i++) {//遍历，输出。
        for (int j = 0; j < cnt[i]; j++) {
            cout << pri[i] << ' ';
        }
    }

    return 0;
}