POJ 3978 Primes(求范围素数个数)
id=3978">http://poj.org/problem? id=3978
题意：
给你一个区间范围A和B，要你求出[A，B]内的素数个数。当中B<=100000。
分析：
首先我们求出2到10W的素数表。把每一个素数按从小到大的顺序保存在prime数组中。然后我们用二分查找找到A的下界和B的上界，然后用上界-下界即为素数个数。
程序实现用了两种筛选法来求素数表。两种筛选法都是基于每一个自然合数都能够分解为：最小素因子p*剩余部分q。
且q>=p。
第一种方式是主要的筛选法，效率慢些。只是也趋近于线性了。
另外一种方式效率是O（n）的。以下解释下另外一种筛选法的原理：
上面的筛选法为什么一定能过滤掉全部的合数呢？
一个合数=它的最小素因子*它的剩下部分（该部分肯定>=最小素因子）
如果当前循环到30。那么因为30=2*15 且15之前被推断过肯定是合数。所以当前prime[30]肯定是1。
同理如果当前循环到合数x，且x中最小素因子为p且x=p*q。
那么之前i==q时的那次循环。必定会标记prime[p*q]=1
从而使得x老早就被标记成了合数。
AC代码：筛选法1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100000;
//筛选法一求素数表
int prime[maxn+5];
int p[maxn+5];
int get_prime()
{
prime[0]=0;
memset(p,0,sizeof(p));
int bound=sqrt(maxn)+1;//边界
for(int i=2;i<=bound;i++)
{
if(p[i]==0)//i是一个素数
{
for(int j=i*i;j<=maxn;j+=i)
p[j]=1;
}
}
for(int i=2;i<=maxn;i++)if(p[i]==0)
prime[++prime[0]]=i;
return prime[0];
} int main()
{
int x=1;
get_prime();
int a,b;
while(scanf("%d%d",&a,&b)==2)
{
if(a==-1&&b==-1)break;
if(a<2) a=0;
if(b<2) b=0;
int L=lower_bound(prime+1,prime+prime[0], a)-prime;
int R=upper_bound(prime+1,prime+prime[0], b)-prime;
printf("%d\n",R-L);
}
return 0;
}
AC代码：筛选法2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100000; //筛选法二求素数
int prime[maxn+5];
int get_prime()
{
memset(prime,0,sizeof(prime));
for(int i=2;i<=maxn;i++)
{
if(prime[i]==0) prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++)
{
prime[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
return prime[0];
} int main()
{
int x=1;
get_prime();
int a,b;
while(scanf("%d%d",&a,&b)==2)
{
if(a==-1&&b==-1)break;
if(a<2) a=0;
if(b<2) b=0;
int L=lower_bound(prime+1,prime+prime[0], a)-prime;
int R=upper_bound(prime+1,prime+prime[0], b)-prime;
printf("%d\n",R-L);
}
return 0;
}