题目描述
N!中质数因子p的个数,就是1~N中每个数含有的质因数p个数
比如1~8中,求质因数2的所有次方之和
8/2=4,所以1-8中2的倍数有4个,即2,4,6,8
其次算4的倍数,8/4=2,所以1-8中4的倍数有2个,即4,8
计算8的倍数,8/8=1,所以8的倍数有1个,即8
此时4+2+1=7即为8!中质因数2的次方数
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
//1~10^6大概有50000个质数
const int N=1000010;
int p[N],st[N],cnt;
void f(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) p[++cnt]=i;
for(int j=1;p[j]*i<=n;j++)
{
st[p[j]*i]=1;
if(i%p[j]==0)
break;
}
}
}
int main()
{
int n;
cin>>n;
//对于每个质数p,找1-n里p的倍数有多少个,1-n里p^的倍数有多少个
f(n);
for(int i=1;i<=cnt;i++)
{
int a=p[i];
int s=0;
for(int j=n;j;j/=a) s+=j/a;
cout<<a<<" "<<s<<endl;
}
return 0;
}