1059 Prime Factors (25 分)质因子 易错题

1059 Prime Factors (25 分)

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p​1​​​k​1​​​​×p​2​​​k​2​​​​×⋯×p​m​​​k​m​​​​.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p​1​​^k​1​​*p​2​​^k​2​​*…*p​m​​^k​m​​, where p​i​​'s are prime factors of N in increasing order, and the exponent k​i​​ is the number of p​i​​ -- hence when there is only one p​i​​, k​i​​ is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

 

具体代码

#include <cstdio> #include <cmath> bool isprime(int a){ if(a<=1)return false; int sqr=(int)sqrt(a); for(int i=2;i<=sqr;i++){ if(a%i==0)false; } return true; } int prime[100020],pnum=0;//pnum为100020以内质数的个数 void findprime(){ for(int i=0;i<100020;i++){ if(isprime(i)==true)prime[pnum++]=i; } } //0到n内的所有质数，并传入数组prime[] struct factor{ int x,cnt;//x为质因子，cnt为质因子的个数 }fac[15]; int main(){ findprime(); int n,num=0;//num为不同的质因子的个数 scanf("%d",&n); if(n==1)printf("1=1"); else{ printf("%d=",n); int sqr=sqrt(n);//因为n的因子只可能在根号n以内 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); } } return 0; }