PAT甲题题解-1059. Prime Factors (25)-素数筛选法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>using namespace std;
/*
范围long int，其实大小范围和int一样，一开始以为是指long long，想这就麻烦了该怎么弄。
而现在其实就是int的范围，那难度当次就不一样了，瞬间变成水题一枚，根号后大小不超过60000。
int 4 -2147438648～+2147438647
long int 4 -2147438648～+2141438647
*/
const int maxn=;
bool isprime[maxn];
int prime[maxn];
int cnt=;void init(){
for(int i=;i<maxn;i++)
isprime[i]=true;
for(int i=;i<maxn;i++){
if(isprime[i]){
prime[cnt++]=i;
for(int j=*i;j<maxn;j+=i)
isprime[j]=false;
}
}
}
int main()
{
int num;
init();
scanf("%d",&num);
printf("%d=",num);
bool first=true;
int factor=;
for(int i=;i<cnt;i++){
int e=;
while(num%prime[i]==){
e++;
num=num/prime[i];
factor++;
}
if(e==)
continue;
if(first){
printf("%d",prime[i]);
first=false;
}
else
printf("*%d",prime[i]);
if(e>)
printf("^%d",e);
}
//以防万一num本身是质数
if(factor==)
printf("%d",num);
return ;
}