题解 | 质数统计

还是第一次发题解=￣ω￣=

思路主要就是先利用埃氏筛标记问题区间内的所有素数，然后用前缀和处理询问。

代码如下：

#include<iostream>
#include<vector>

std::vector<bool> num(10e6+1, true);
std::vector<int> count(10e6+1, 0);

//埃氏筛
void prime_find()
{
    for(int i = 2; i <= 10e6; i++)
    {
        if(num[i] == true)
        {
            for(int j = 2; i * j <= 10e6; j++)
            {
                num[i * j] = false;
            }
        }
    }
    return;
}

//用一个数组记录截至到数i处的质数总数
void partial_sum()
{
    int sum = 0;
    for(int i = 2; i <= 10e6; i++)
    {
        if(num[i] == true)
        {
            sum++;
        }
        count[i] += sum;
    }
}

int main()
{
    int n;
    std::cin >> n;
    prime_find();
    partial_sum();
    for(int i = 0; i < n; i++)
    {
        int l, r;
        std::cin >> l >> r;
        //利用类似前缀和的方法输出区间内的质数数量
        std::cout << count[r] - count[l -1] << "\n";
    }
    return 0;
}