题解 | 质数因子

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

vector<int> primes;
bool* vt=(bool*)malloc(sizeof(bool)*(2e5+1));

void getPrime(int n=(2e5)){
    primes.push_back(2);
    for(int i=2;i<=n;i+=2){
        vt[i]=true;
    }
    for(int i=3;i<=n;i+=2){
        if(!vt[i]){
            primes.push_back(i);
            vt[i]=false;
        }
        for(auto& prime:primes){
            if(i*prime>n)
                break;
            vt[i*prime]=true;
        }
    }
}

int main() {
    int n;
    cin>>n;
    getPrime();
    for(auto& prime:primes){
        if(n==1)
            break;
        while(n%prime==0){
            cout<<prime<<" ";
            n/=prime;
        }
    }
    if(n!=1)
        cout<<n;
}

首先用埃氏素数筛法把小于sqrt(n)的素数全部筛选出来。因为n分解出的超过sqrt(n)的质因子数量最多一个，反证法：假设如果有两个a和b，那n>=a*b>sqrt(n)*sqrt(n)=n,得到n>n，显然是错误的，因此超出sqrt(n)的质因子最多一个。当我们遍历完所有小于sqrt(n)的素数后，n仍然没有被分解完，剩下的部分一定是素数，不需要判断直接输出即可。