题解 P2043 【质因子分解】

· · 题解

这道赤裸裸的数论，一个比较简单的办法，找质数加判断是不是整除i，直到该n！变成1

上思路

主要思路


 1.筛素数，因为n的范围是10000，所以要筛到10000，这样就不怕     素数不够了

 2.开始分解n！，不用把n的阶乘求出来，只需要一个循环，从2循     环到n，把每个数分解的变成1即可。

 3.把所有质因数输出来就可以了

我的代码：


1.a数组存n！的质因数，pd数组判断质数

2.初始所有数都是质数，a数组清空,输入n

3.开始筛素数，循环只需从2循环到100就可以了

  筛掉所有质数的倍数，剩下的就是合数

4.开始分解n！，i从2到n，b是当前的i

  质因数分解b，直到b变成1

5.输出有质因数和个数就可以了

上代码

#include<cstdio>
#include<cstring>
#include<algorithm>
int n,a[10001];
bool pd[10001];
int main()
{
    memset(pd,1,sizeof(pd));
    memset(a,0,sizeof(a));
    scanf("%d",&n);
    for(int i=2;i<=100;i++)
      if(pd[i])
        for(int j=2;i*j<=10000;j++)
          pd[i*j]=0;
    for(int i=2;i<=n;i++)
    {
        int b=i;
        for(int j=2;j<=n;j++)
          if(pd[j])
            while(b%j==0)
            {
                a[j]++;
                b/=j;   
            }
    }
    for(int i=2;i<=n;i++)
      if(a[i]!=0)
        printf("%d %d\n",i,a[i]);
    return 0;
}