洛谷 P1075 [NOIP2012 普及组] 质因数分解

参考代码

#include
#define int long long
using namespace std;
int n,m,p[1000005],c[1000005];
signed main(){
    cin>>n;
    int N=n;
    for(int i=2;i<=sqrt(N);i++){
        if(!(n%i)){
            p[++m]=i;
            c[m]=0;
            while(!(n%i)){
                n/=i;
                c[m]++;
            }
        }
    }
    if(n>1){
        p[++m]=n;
        c[m]=1;
    }
    for(int i=1;i<=m;i++){
        if(i==m){
            if(c[i]==1){
                cout<             }
            else{
                cout<             }    
            continue;        
        }
        if(c[i]==1){
            cout<         }
        else{
            cout<         }
    }
    return 0;
}

代码解读

具体地，我们可以枚举 2到 根号n中所有数i，如果i能整除n，则不断地从n中除掉i，直到i不再能整除n，在这个过程中，我们同时需要统计被除掉的每个i的个数。注意，本题中 的规模为 2≤n≤10的12次方，需要开 long long。

-->for(int i=2;i<=sqrt(N);i++){
        if(!(n%i)){
            p[++m]=i;
            c[m]=0;
            while(!(n%i)){
                n/=i;
                c[m]++;
            }

    for(int i=1;i<=m;i++){
        if(i==m){
            if(c[i]==1){
                cout<             }
            else{
                cout<             }    
            continue;        
        }
        if(c[i]==1){
            cout<         }
        else{
            cout<         }
    }
    return 0;
}-->输出所有因数。