题解 | #质数因子#

暴力

#include<iostream>
using namespace std;
#include<cmath>
int isPrime(int n) {
    if (n <= 3) {
        return n > 1;
    }
    //只需判断一个数能否被小于sqrt(n)的奇数整除
    int sqrt0 = sqrt((float)n);
    for (int i = 3; i <= sqrt0; i += 2) {
        if(n % 2 == 0 || n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main(){
    int n;
    cin>>n;
    if(n == 1)
        return 0;
    if(n<=3)
        cout<<n<<endl;
    int i = 2;
    while(n){
        if(isPrime(n))  {cout<<n<<" "; break;}
        if(n%i == 0){
            cout<<i<<" ";
            n = n/i;
        }
        else{
            while(!isPrime(++i));
        }
            
    }
    cout<<endl;
}