求区间内素数个数问题

题目描述

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("%d\n",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("%d\n",s[b]);
		else printf("%d\n",s[b]-s[a-1]);
	}
}