n!的分解

只看该作者 · 2019-9-14 18:02

Description
给你一个数 n (1 < n <= 1000000) ,求 n! (n的阶乘)的质因数分解形式，质因数分解形式为
n=p1^m1*p2^m2*p3^m3……
* 这里 p1 < p2 < p3 < …… 为质数
* 如果 mi = 1, 则 ^ mi 就不需要输出

只看该作者 · 2019-9-14 18:03

Input

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

Output

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

只看该作者 · 2019-9-14 18:03

Sample Input

6
7
0

Sample Output

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

只看该作者 · 2019-9-14 18:04

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

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

只看该作者 · 2019-9-14 18:05

复制

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

}

只看该作者 · 2019-9-14 18:05

作者：Matrix海子
　　　　
出处：http://www.cnblogs.com/dolphin0520/
　　　　
本博客中未标明转载的**归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在**页面明显位置给出原文连接，否则保留追究法律责任的权利。

n!的分解

相关下载

相关帖子