prime
題目描述
給定區(qū)間[L, R](L <= R <= 2147483647两波， R-L <= 1000000)析孽，請計(jì)算區(qū)間中
素?cái)?shù)的個(gè)數(shù)乃摹。
輸入輸出
輸入
兩個(gè)數(shù) L 和 R云茸。
輸出
一行善镰，區(qū)間中素?cái)?shù)的個(gè)數(shù)妹萨。
樣例
樣例輸入
2 11
樣例輸出
5
說明
時(shí)空限制
時(shí)間限制 1s/testcase
空間限制 32MB
思路
R-L<=1000000
L <= R <= 2147483647
時(shí)間上用質(zhì)數(shù)篩能過
求出2~45000的所有質(zhì)數(shù)（sqrt(2147483647)大約是4300+）
然后將所有是這些質(zhì)數(shù)的倍數(shù)的數(shù)刪掉年枕，剩下的就是質(zhì)數(shù)
空間上只有32mb炫欺，數(shù)組不能開太大，考慮到R-L<=1000000
完全可以只開到100005熏兄，之后對于大于100000的L和R品洛，在存質(zhì)數(shù)時(shí)
減去L即可。
代碼
/*
b[i]==1 i不是質(zhì)數(shù)
b[i]==0 i是質(zhì)數(shù)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int i,j,k,l,t,n,m,ans;
int zhi[100005];
bool b[100005],z[1000005];
inline int read() {
int x=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
return x*w;
}
int main() {
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
for(i=2; i<=sqrt(100000); i++) {
if(!b[i]) {
for(j=2; j<=100000/i; j++) {
b[i*j]=1;
}
}
}
for(i=2; i<=100000; i++)if(!b[i])zhi[++zhi[0]]=i;
n=read();
m=read();
for(i=1; i<=zhi[0]; i++) {
for(j=max(n/zhi[i],1); j<=m/zhi[i]; j++) {
if(j==1)continue;
if(j*zhi[i]<n)continue;
z[zhi[i]*j-n]=1; //平移數(shù)組摩桶，控制空間大小
}
}
for(i=n-n; i<=m-n; i++) {
if(!z[i])++ans;
}
printf("%d\n",ans);
return 0;
}
