#6235. 區間素數個數

題目描述

求?1～n 1\sim n1～n?之間素數個數。

輸入格式

一行一個數?n nn?。

輸出格式

一行一個數，表示答案。

樣例

樣例輸入

10

樣例輸出

4

樣例解釋 1

2,3,5,72,3,5,72,3,5,7

數據范圍與提示

對于?100% 100\%100%?的數據，2≤n≤1011 2 \leq n \leq 10^{11}2≤n≤10?11??。

?

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 316228 using namespace std; long long n; bool vis[maxn]; int lim,p[27294],sum[maxn],last[maxn*2],cnt; long long val[maxn*2],f[maxn*2]; void prepare(){for(int i=2;i<=lim;i++){if(!vis[i])p[++p[0]]=i;sum[i]=sum[i-1]+!vis[i];for(int j=1;j<=p[0]&&i*p[j]<=lim;j++){vis[i*p[j]]=1;if(i%p[j]==0)break;}} } int main(){cin>>n;lim=sqrt(n);prepare();for(long long i=1;i<=n;i=n/(n/i)+1)val[++cnt]=n/i;reverse(val+1,val+cnt+1);copy(val+1,val+cnt+1,f+1);for(int i=1;i<=p[0];i++){for(int j=cnt;j>=1;j--){long long k=val[j]/p[i];long long pos=k<=lim?k:cnt+1-n/k;if(k<p[i])break;f[j]-=f[pos]+last[pos]-i+1;last[j]=i;}}printf("%lld",sum[lim]+f[cnt]-1);return 0; }

?

轉載于:https://www.cnblogs.com/thmyl/p/8960745.html

總結

以上是生活随笔為你收集整理的loj #6235. 区间素数个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。