1059 Prime Factors

link

解法：

只需要枚举质数能否整除n。

提前筛除sqrt(n)以内的质数，然后到时候只需要枚举这些质数i能否整除n,若能整除，n=n/i;

最后n必定是一个质数或是1。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <queue>
#include <cmath>
# define LL long long
using namespace std;

vector<LL> isprime;
LL N;
int main(){
    cin>>N;
    LL q=sqrt(N);
    isprime=vector<LL>(q+1,1);
    if(N==1){
        printf("1=1");
        return 0;
    }
    for(LL i=2;i<=q;i++){
        if(isprime[i]){
            for(LL j=i;i*j<=q;j++){
                isprime[i*j]=0;
            }
        }
    }
    printf("%lld=", N);
    bool isfirst=true;
    for(LL i=2;i<=q;i++){
        if(N<2) break;
        if(isprime[i]){
            int cnt=0;
            while(N>=2 && N%i==0){
                cnt++;
                N/=i;
            }
            if(cnt>0){
                if(isfirst){
                    isfirst=false;
                    printf("%lld",i);
                }else{
                    printf("*%lld",i);
                }
                if(cnt>1) printf("^%d", cnt);
            }
        }
    }
    if(N>1){
        if(isfirst){
            isfirst=false;
            printf("%lld",N);
        }else{
            printf("*%lld",N);
        }
    }
    return 0;
}