n!的分解 soj 2666

时间：2011-04-12 来源：海子

                                                         分解 n! Description

给你一个数 n (1 < n <= 1000000) ,求 n! (n的阶乘)的质因数分解形式，质因数分解形式为

n=p1^m1*p2^m2*p3^m3……

*  这里 p1 < p2 < p3 < …… 为质数
*  如果 mi = 1, 则   ^ mi   就不需要输出 

Input

输入是多case的，每行一个数n，1 < n <= 1000000，当n等于0时输入结束

Output

每个n输出一行，为它的质因数分解形式

Sample Input

6
7
0

Sample Output

6=2^4*3^2*5
7=2^4*3^2*5*7

题意：给出n,将n!分解成质因子相乘的形式。

在这里如果每次给出n并且去求小于n的质因子，肯定会超时，因此可以先把1000000以内的质数求出来存在数组里，后面需要直接调用，并且这里求质数不能采用简单的试除法去求，那样效率很低，这里我们采用筛选法求解。

#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;
}