PAT 1059 Prime Factors (25 分) 素数表

#include 
#include 
#include 
using namespace std;
vectorprime(50000,1);
int main() {   
    for(int i=2;i*i<50000;i++)
        for(int j=2;j*i<50000;j++)
            prime[j*i]=0;             //50000内任意可以分解成j*i的数都不是素数，而且其中一个素数i必定小于sqrt(50000)
    long int a;   
    scanf("%ld",&a);
    printf("%ld=",a);
    if(a==1)printf("1");
    bool state=false;
    for(int i=2;i<50000&&a>2;i++){
        int cnt=0,flag=0;
        while(prime[i]==1&&a%i==0){         //从小到大可以分解出因数i,i可能不止一个，一直循环除i
            cnt++;
            a=a/i;
            flag=1;
        }
        if(flag){
            if(state)printf("*");     //第二个因数开始带*
            printf("%d",i);
            state=true;
        }
        if(cnt>=2)printf("^%d",cnt);
    }
    if(a>1)printf("%s%ld",state?"*":"",a);  //state表示可以分解，a是最后一个质数因子，否则直接打印n
    system("pause");
    return 0;
}