有的时候，题目要求我们筛选出一段区间内的素数，我们就需要掌握一种素数筛选的方法。

如果用上一节素数判定的方法去判定每一个数是不是素数的话。
复杂度是O(n*sqrt(n))，大概能处理到10000以内的数。

如果题目要求的范围更大，那么我们就需要一种更为高效的筛选法。
掌握下面这一种线性复杂度的筛选方法就足够我们应对任何情况。

// 线性素数筛选  prime[0]存的是素数的个数  
const int maxn = 1000000 + 5;  
int prime[maxn];  
void getPrime() {  
    memset(prime, 0, sizeof(prime));  
    for (int  i = 2; i <= maxn; i++) {  
        if (!prime[i]) prime[++prime[0]] = i;  
        for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {  
            prime[prime[j] * i] = 1;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}  

素数判定
题目描述：
给你两个数a、b,现在的问题是要判断这两个数组成的区间内共有多少个素数
输入描述：
多组测试数据。 每个测试数据输入两个数a、b。(2<=a,b<=1000)
输出描述：
输出该区间内素数的个数。
输入样例#:
2 4
4 6
输出样例#:
2
1
题目来源：
DreamJudge 1102

题目解析：这道题的数据范围不大，我们可以用挨个暴力判断的方法来解决。我们假设这道题的数据范围很大，使用素数筛选的方法来解决这个问题。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
// 线性素数筛选  prime[0]存的是素数的个数  
const int maxn = 1000000 + 5;  
int prime[maxn];  
void getPrime() {  
    memset(prime, 0, sizeof(prime));  
    for (int  i = 2; i <= maxn; i++) {  
        if (!prime[i]) prime[++prime[0]] = i;  
        for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {  
            prime[prime[j] * i] = 1;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}  
int main() {  
    getPrime();//先进行素数筛选预处理  
    int a, b;  
    while (scanf("...

练习题目

DreamJudge 1375 素数