1. 因为我们有一个质因子p已经出现过了,所以我们并需要乘以2.(乘以二,是因为我们是在统计质因子出现的次数)

这句话错误的,已经删除了.

原题链接
更好的阅读体验

题目描述

给定整数 N ，试把阶乘 $N!$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $p_i$ 和 $c_i$ 即可。

输入格式
一个整数$N$。

输出格式
$N!$ 分解质因数后的结果，共若干行，每行一对$p_i,c_i$，表示含有${p_i}^{c_i}$项。按照pi从小到大的顺序输出。

数据范围
$1≤N≤10^6$

样例

输入样例：
5
输出样例：
2 3
3 1
5 1

样例解释
$5!=120=2^3∗3∗5$

数学性质(质因数分解)

首先可以排出的方法,就是把1~N中每一个数字都质因数分解,这种方法复杂度太高了,淘汰.

正确的数学姿态是:我们发现N!中质数因子p的个数,就是1~N中每个数含有的质因数p个数.既然如此的话,那么我们发现,至少有一个质因子p的显然有$[\frac{n}{p}]$个,而至少有两个质因子p数的显然是有$[\frac{n}{p^2}]$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long p[N],vis[N],n,m;
long long zs(long long n)//素数筛
{
    for(long long i=2;i<=n;i++)
    {
        if (!vis[i])
            p[++p[0]]=i;
        for(long long j=2;j<=n/i;j++)
            vis[i*j]=1;
    }
}
long long power(long long a,long long b)//快速幂
{
    long long ans=1;
    while(b)
    {
        if (b&1)
            ans=ans*a;
        a*=a;
        b>>=1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    zs(n);
    for(long long i=2;i<=n;i++)
        if (!vis[i])
        {
            long long ans=0;
            cout<<i<<" ";
            for(long long k=1;power(i,k)<=n;k++)//统计p出现的次数
                ans=ans+n/power(i,k);
            cout<<ans<<endl;
        }
    return 0;
}