题目:https://ac.nowcoder.com/acm/problem/51043
思路:先将n以内的质数进行打表,然后计算每一个质数的贡献次数。
代码:
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<map> #include<vector> #include<set> #include<utility> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1e6+5; const LL mod=1e9+7; int read() { char ch=getchar();int x=0,f=1; while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);} LL fpow(LL a,LL b) { LL res=1; while(b) { if(b&1) res=(res*a)%mod; a=(a*a)%mod; b>>=1; } return res; } int p[maxn]; int pr[maxn]; int cnt=0; void init(int n) { for(int i=2;i<=n;++i) { if(!p[i]) pr[cnt++]=i; for(int j=0;j<cnt;++j) { if(i*pr[j]>n) break; p[i*pr[j]]=1; if(i%pr[j]==0) break; } } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); // cout<<"Accepted!\n"; int n; cin>>n; init(n); for(int i=0;i<cnt;++i) { LL res=0; for(LL j=pr[i];j<=n;j*=1LL*pr[i]) res+=1LL*n/j; cout<<pr[i]<<" "<<res<<"\n"; } return 0; }