给定区间 [L,R](1≤R<(1<<30) R−L≤1e6 ),请计算区间中素数的个数。
筛出 sqrt(R) 的质数p, 遍历 L~R 的数,看能否被p 约分,也就是合数,打个标记
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> using namespace std ; const int M=1e6+30; #define int long long int vis[M]; int b[M],prime[M],tot,n; void init(int top){ memset(b,1,sizeof b); b[1]=0; int i,j; for(i=2;i<=top;i++){ if(b[i]) prime[++tot]=i; for(j=1;j<=tot&&i*prime[j]<=top;j++){ b[i*prime[j]]=0; if(i%prime[j]==0) break; } } } signed main(){ int L,R; cin>>L>>R; L= L==1?2:L; init(1e6); for(int i=1;i<=tot;i++){ int t=prime[i]; int k=(L+t-1)/t*t>2*t?(L+t-1)/t*t:2*t; for(int j=k;j<=R;j+=t) vis[j-L+1]=1; } int cnt=0; for(int i=L;i<=R;i++) if(vis[i-L+1]==0) cnt++; cout<<cnt; }
标签:P1835,int,init,long,素数,密度,1e6,include From: https://www.cnblogs.com/towboa/p/17305822.html