题解：SP3505 CPRIME - Prime Number Theorem

思路：

这一题题意很明确，就是给一个

n

，求下面一个式子

因为多测且

n

最大只有

10^8

，所以可以预处理范围内每个

n

的

\pi (n)

，最后输出答案即可。

代码：

CPP

#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

一大就算不对？

CPP

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];
		}
	}
}

题解：SP3505 CPRIME - Prime Number Theorem

文章操作

思路：

代码：

相关推荐

评论

题解：SP3505 CPRIME - Prime Number Theorem