求区间内素数个数问题

题目描述

Description
给定两个非负整数a，b，其中0<= a,b<=1,000,000，请计算这两个数之间有多少个素数。限制：Time Limit : 1000 MS Memory Limit : 65536 KB

输入
第一行是一个整数K（1<=K<=1000），表示有多少个样例，每个样例占一行，是两个整数a和b，每个整数之间用一个空格隔开。

输出
每行输出一个样例的结果。

Sample Input
2
2 3
17 19
Sample Output
2
2

解题思路

这个题目思路很简单，就是判断素数，然后计算个数。
主要的问题是如何判断某个数是否是素数，以及采用什么方式来计算个数

首先这个题目中a,b的值可能会很大，所以常规的求素数的方法是不可取的。相对简单的一个方法就是在循环外面进行打表，之后只要看对应下标的值来判断该数是否为素数就好了。现有一个数组noprime，下标 i 对应的noprime[ i ] 为1，则表示 i 为非素数，对应的noprime[ i ] 为0，则表示 i 为素数。（若一个数为某个数的倍数，那么这个数一定是非素数）

int noprime[1000050]; noprime[0] = 1;  noprime[1] = 1; for(int i = 2; i<= 1000000; i++) { if(!noprime[i]) { for(int j = 2*i; j<= 1000000; j+=i) {    noprime[j] = 1; } } } 

代码如下

第一种方法

打表后直接循环a到b，判断每一个数是否为素数。

#include<cstdio> #include<algorithm> using namespace std; int noprime[1000050]; int main() {  noprime[0] = 1;   noprime[1] = 1; //1表示非素数，0表示素数  for(int i = 2; i<= 1000000; i++) { if(!noprime[i]) { for(int j = 2*i; j<= 1000000; j+=i) {     noprime[j] = 1; } } } int k; scanf("%d",&k); while(k--) { int a,b; scanf("%d%d",&a,&b); if(a>b) swap(a,b); int num = 0; for(int i = a; i<= b; i++) { //直接在a和b范围内数素数的个数 if(!noprime[i]) num++; } printf("%dn",num); } return 0; } 

第二种方法

打表后，采用前缀和算法直接得出素数的个数。用一个数组s[ ]记录到该数为止前面一共有多少个素数，那么若要得出a 到 b的素数个数，可以直接用s[b]-s[a-1]得出。

比如说现在判断0到7的素数个数：
0为非素数，初始化s[0]=0;
1为非素数，所以到1为止一共有0个素数，就是在s[0]的基础上加0；
2为素数，到2为止一共有1个素数，就是在s[1]的基础上加上1；
3为素数，到3为止一共有2两个素数，就是在s[2]的基础上加上1；
…

所以我们注意到我们只需要考察当前这个数是否为素数，若为素数，就需要在前面得出的个数上加1，若不是素数，则仍保持为之前得出的数字。这样s[ i ]表示的就是到目前 i 这个位置为止，素数的个数。

int s[1000050]; s[0] = 0; for(int i = 1; i<= 1000000; i++) { if(noprime[i]==1) s[i] = s[i-1]; else if(noprime[i]==0) s[i]=s[i-1]+1; } 

总的代码如下。

#include<cstdio> #include<algorithm> using namespace std; int s[1000050]; int noprime[1000050]; int main() {  noprime[0] = 1;   noprime[1] = 1; for(int i = 2; i<= 1000000; i++) { if(!noprime[i]) { for(int j = 2*i; j<= 1000000; j+=i) {     noprime[j] = 1; } } }  s[0] = 0; for(int i = 1; i<= 1000000; i++) { if(noprime[i]==1) s[i] = s[i-1]; else if(noprime[i]==0) s[i]=s[i-1]+1; } int k; scanf("%d",&k); while(k--) { int a,b; scanf("%d%d",&a,&b); if(a>b) swap(a,b); if(a==0) printf("%dn",s[b]); else printf("%dn",s[b]-s[a-1]); } }