给定区间[L，R](L≤R≤2147483647,R-L≤1000000)，请计算区间中素数的个数。
输入格式：
两个数L和R。
输出格式：
一行，区间中素数的个数。
Solution:
本题比较模板（水）。
因为$int_{max}$范围内的合数只需用$\sqrt {int_{max}}\leq 50000$内的质数就能筛出。
于是，预处理出$50000$内的质数，然后埃式筛掉$[l,r]$范围内的合数就好了，随便瞎搞一下就好了。
最后统计一下质数个数并输出。
代码：
1 #include<bits/stdc++.h> 2 #define il inline 3 #define ll long long 4 #define For(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++) 5 #define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--) 6 using namespace std; 7 const int N=50005,M=1000005; 8 int l,r,prime[N+5],cnt; 9 bool isp[N+5],isprime[M+5]; 10 11 il void init(){ 12 For(i,2,N){ 13 if(!isp[i]) prime[++cnt]=i; 14 for(int j=1;j<=cnt&&prime[j]*i<=N;j++){ 15 isp[prime[j]*i]=1; 16 if(i%prime[j]==0)break; 17 } 18 } 19 } 20 21 il void solve(){ 22 ll p,q; 23 For(i,1,cnt){ 24 if(prime[i]>r)break; 25 p=ceil(l*1.0/prime[i]),q=ceil(r*1.0/prime[i]); 26 if(p==1)p=2; 27 for(int j=p;j<=q&&prime[i]*j<=r;j++) 28 isprime[prime[i]*j-l+1]=1; 29 } 30 int tot=0; 31 For(i,1,r-l+1) if(!isprime[i]) tot++; 32 cout<<tot; 33 } 34 35 int main(){ 36 init(); 37 cin>>l>>r; 38 solve(); 39 return 0; 40 }
原文：https://www.cnblogs.com/five20/p/9231418.html