主要思路

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

没什么好讲的吧~

直接上

$AC ~ Code$：

#include <bits/stdc++.h>

#define ll long long
#define re register int

using namespace std;

ll n, a[10005];

int main()
{

    // freopen("P2043.in", "r", stdin);
    // freopen("P2043.out", "w", stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;

    for (re i = 2; i <= n; i++)
    {
        int x = i;
        for (re j = 2; j <= n; j++)
        {
            while (x % j == 0)
            {
                a[j]++;
                x /= j;
            }
        }
    }
    
    for (re i = 1; i <= n; i++)
        if (a[i] != 0)
            cout << i << " " << a[i] << endl;
    return 0;
}

直接分解 $N!$ 不现实，也没有必要。我们可以分别对 $2$~$n$ 一 一找出它们的质因子（这一部分的代码详解可以去看看这一题的题解)，找到一个质因子 $i$ 就令ans[i]++，最后输出 $ans$ 数组即可。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=10005;
ll n,ans[N];
int main(){
    scanf("%lld",&n);
    for(ll k=2;k<=n;k++){
        ll i=k;
        for(ll j=2;j*j<=i;j++) // 找出k的质因子
            while(i%j==0)
                i/=j,ans[j]++;
        if(i>1)
            ans[i]++;
    }
    for(ll i=2;i<=n;i++) // 输出ans数组
        if(ans[i])
            printf("%lld %lld\n",i,ans[i]);
    return 0;
}

upd. 2024.3.29 更新了更短、更优的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000005;
int sum,n,vis[N];
int main(){
	cin>>n; 
	for (int i=2;i<=n;++i){//求出1~N之间的质数 
		if (vis[i]) continue;
		for (int j=i+i;j<=n;j+=i)
			vis[j]=1;//筛质数
		sum=0;
		for (int j=i;j<=n;j*=i)
			sum+=n/j;//计算式子 
		cout<<i<<' '<<sum<<"\n";
	}
}