PAT A1059 质因子分解

这里需要注意一下，long int就是int，一样的。。。#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<math.h>using namespace std;using std::vector;const int maxn=100010;struct factor{ int x; int cnt;}fac[10];bool is_prime(int n){ if(n==1) return false; int sqr=(int)sqrt(1.0n); for(int i=2;i<=sqr;i++){ if(n%i==0) return false; } return true;}int prime[maxn],pNum=0;void Find_Prime(){ for(int i=1;i<maxn;i++){ if(is_prime(i)==true){ prime[pNum++]=i; } }}int main(){ Find_Prime(); int n,num=0; scanf("%d",&n); if(n==1) printf(“1=1”); else{ printf("%d=",n); int sqr=(int)sqrt(1.0n); for(int i=0;i<pNum&&prime[i]<=sqr;i++){ if(n%prime[i]==0){ fac[num].x=prime[i]; fac[num].cnt=0; while(n%prime[i]==0){ fac[num].cnt++; n/=prime[i]; } num++; } if(n==1) break; } if(n!=1){ fac[num].x=n; fac[num++].cnt=1; } for(int i=0;i<num;i++){ if(i>0) printf("*"); printf("%d",fac[i].x); if(fac[i].cnt>1){ printf("^%d",fac[i].cnt); } } } system(“pause”); return 0;}