Prime

题目：Prime
来源：哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛）

解题思路

在一个闭区间 [a, b] 内，有多少个质数？

筛法求素数：把从 1 开始的、某一范围内的正整数从小到大顺序排列，1 不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

C++代码

#include<iostream>
using namespace std;

const int N = 1e7+1;
int sum[N];
int visited[N];

void isPrime(){
    sum[1] = 0;
    for(int i=2; i<N; ++i){
        if(!visited[i]){
            sum[i] = sum[i-1] + 1;
            for(int j=i+i; j<N; j+=i)
                visited[j] = 1;
        }
        else
            sum[i] = sum[i-1];
    }
}

int main(){
    isPrime();
    int T;
    cin >> T;
    int a, b;
    for(int i=0; i<T; ++i){
        cin >> a >> b;
        cout << sum[b] - sum[a-1] << endl;
    }
}