PAT甲级1059 Prime Factors

PAT甲级1059 Prime Factors

AC代码

#include<stdio.h>
#include<math.h>
int prime[50001],cn=0,p[100001]={0};
void Prime()
{for(int i=2;i<100001;i++){if(p[i]==0){prime[cn++]=i;for(int j=i+i;j<100001;j+=i){p[j]=1;}}}
}
int main()
{Prime();	int n,flag=0;scanf("%d",&n);if(n==1) printf("1=1");else{printf("%d=",n);for(int i=0;i<cn&&prime[i]<=sqrt(n);i++){if(n%prime[i]==0){if(flag==0) flag=1;else printf("*");printf("%d",prime[i]);int cp=0;while(n%prime[i]==0){cp++;n/=prime[i];}if(cp>1) printf("^%d",cp);}}if(n!=1){if(flag==0) printf("%d",n);else printf("*%d",n);}}
}