我觉得都不用过多解释,看代码就懂了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int read()
{
int x=0;
char s=getchar();
while(s<'0'||s>'9')
{
s=getchar();
}
while(s>='0'&&s<='9')
{
x=(x<<3)+(x<<1)+s-48;
s=getchar();
}
return x;
}
int prime[N],v[N];
int cnt;
void getprime(int n)
{
for(int i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]*i<=n&&prime[j]<=v[i];j++)
v[prime[j]*i]=prime[j];
}
}
int n;
ll c[N];
int main()
{
int a,u;
n=read();
getprime(n);
for(int i=2;i<=n;i++) c[i]=1;
for(int i=n;i>=2;i--)
if(v[i]!=i)
{
c[v[i]]+=c[i];
c[i/v[i]]+=c[i];
}
for(int i=1;i<=cnt;i++)
printf("%d %lld\n",prime[i],c[prime[i]]);
return 0;
}
标签:int,197,long,阶乘,Acwing,getchar
From: https://www.cnblogs.com/dingxingdi/p/17641749.html