题解：SP3505 CPRIME - Prime Number Theorem

zby0501_ · 2025-02-18 21:38:33 · 题解

思路：

这一题题意很明确，就是给一个 n，求下面一个式子

因为多测且 n 最大只有 10^8，所以可以预处理范围内每个 n 的 \pi (n)，最后输出答案即可。

代码：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const long long N=1e8+10;
long long pri[N],phi[N],cnt;
long long n;
bool vis[N];
void f(){
    vis[1]=vis[0]=1;
    for(long long i=2;i<N;i++){
        if(!vis[i]) pri[++cnt]=i;phi[i]=cnt;
        for(long long j=1;j<=cnt && pri[j]*i<=N;j++)
            vis[i*pri[j]]=1;
    }
}
signed main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    f();
    while(1){
        scanf("%lld",&n);
        if(n==0) break;
        double ans=n*1.0/log(n*1.0);
        ans=abs(ans-phi[n])*100.0/phi[n];
        printf("%.1lf\n",ans);
    }
    return 0;
}

最后有一点疑问：为什么下面的代码 n 一大就算不对？

void f(){
    phi[1]=1;
    for(long long i=2;i<N;++i){
        if(vis[i]==0) pri[++cnt]=i,phi[i]=cnt;
        for(long long j=1;j<=cnt && pri[j]<=N/i;++j){
            vis[i*pri[j]]=1;
            if(!(i%pri[j])){
                phi[i*pri[j]]=pri[j]*phi[i];
                break;
            }
            else phi[i*pri[j]]=(pri[j]-1)*phi[i];
        }
    }
}