- #include<iostream>
- #include<math.h>
- using namespace std;
- bool isprime[1000001];
- int prime[80000];
- int num=0;
- void getPrime() //用筛选法求算素数
- {
- int i,j;
- for(i=0;i<1000001;i++)
- {
- isprime[i]=true;
- }
- for(i=2;i<=1000;i++) //如果isprime[i]==true,即i是素数，那么i，2*i，3*i必定不是素数
- {
- for(j=i+i;j<=1000000;j+=i)
- {
- if(isprime[i]==true)
- isprime[j]=false;
- }
- }
- for(i=2;i<1000001;i++)
- {
- if(isprime[i]==true)
- {
- prime[num++]=i;
- }
- }
- }
- int count(int n,int k) //求n!中含有某因子k的个数
- {
- int num=0;
- while(n)
- {
- num+=n/k;
- n=n/k;
- }
- return num;
- }
- int main(void)
- {
- int n;
- getPrime();
- while(scanf("%d",&n)==1&&(n>1&&n<=1000000))
- {
- int i,j;
- int m;
- for(i=0;i<num;i++)
- {
- if(prime[i]>n)
- break;
- }
- printf("%d=",n);
- for(j=0;j<i-1;j++)
- {
- m=count(n,prime[j]);
- if(m>1)
- printf("%d^%d*",prime[j],m);
- else
- printf("%d*",prime[j]);
- }
- m=count(n,prime[j]);
- if(m>1)
- printf("%d^%d\n",prime[j],m);
- else
- printf("%d\n",prime[j]);
- }
- return 0;
- }
| 
楼主
