POJ 3978 Primes(求范围素数个数)
?id=3978
题意：
给你一个区间范围A和B，要你求出[A，B]内的素数个数。其中B<=100000。
分析：
首先我们求出2到10W的素数表，，把每个素数按从小到大的顺序保存在prime数组中。然后我们用二分查找找到A的下界和B的上界，然后用上界-下界即为素数个数。
第一种方式是基本的筛选法，效率慢些，不过也趋近于线性了。
第二种方式效率是O（n）的。下面解释下第二种筛选法的原理：
上面的筛选法为什么一定能过滤掉所有的合数呢？
一个合数=它的最小素因子*它的剩下部分（该部分肯定>=最小素因子）
假设当前循环到30，那么由于30=2*15 且15之前被判断过肯定是合数，所以当前prime[30]肯定是1。
同理假设当前循环到合数x，且x中最小素因子为p且x=p*q。
那么之前i==q时的那次循环，必然会标记prime[p*q]=1
从而使得x老早就被标记成了合数。
#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;}
#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;}
什么天荒地老，什么至死不渝。都只是锦上添花的借口…
