【Hit 2276（数论、素数）】
【原题链接】
http://acm-hit.sunner.cn/index.php?option=com_wrapper&Itemid=39
（不准确，需去hit找那个题号）
【题目大意】
输入l、r输出L、R之间的素数个数(L <= R <= 2147483647, R - L <= 1000000)
【解题思想】
数据范围比较大，需要充分利用判定素数的方法，可知一个数x如果不是素数，当且仅当有一个小于等于sqrt(x)的数y，使得x%y==0，因此可以利用sqrt(2147483647)去做整体的判断，由于R-L有范围，因此可遍历这个范围内的数字筛去小于sqrt(r)的素数的倍数，没有被筛去的就是素数，遍历数出素数的个数即可。
[code]
#include <iostream>
#include <cmath>
using namespace std;
unsigned long prime(unsigned long a[],unsigned long n)
{
unsigned long i,j,k,x,num,*b;
n++;
n/=2;
b=new unsigned long[(n+1)*2];
a[0]=2;a[1]=3;num=2;
for(i=1;i<=2*n;i++)
b[i]=0;
for(i=3;i<=n;i+=3)
for(j=0;j<2;j++)
{
x=2*(i+j)-1;
while(b[x]==0)
{
a[num++]=x;
for(k=x;k<=2*n;k+=x)
b[k]=1;
}
}
return num;
}
unsigned long pr[50000];
bool isHave[1100000];
int main()
{
unsigned long l,r,i,j,ans;
prime(pr,50000);
while(scanf("%ld%ld",&l,&r)!=EOF)
{
ans=0;
for(i=0;i<=r-l;i++) isHave[i]=1;
for(i=0;pr[i]*pr[i]<=r;i++)
{
if(l%pr[i]) j=(l/pr[i]+1)*pr[i];
else j=l;
for(;j<=r;j+=pr[i])
{
if(j!=pr[i]) isHave[j-l]=0;
}
}
for(i=0;i<=r-l;i++)
if(isHave[i]) ans++;
printf("%ld\n",ans);
}
return 0;
}
[\code]