《P1835 素数密度》

标题配景

UPD:

• 2024.8.12：加入一组 Hack 数据。
  

标题形貌

给定 L,R，请盘算区间 [L,R] 中素数的个数。
1≤L≤R<231，R−L≤106。
输入格式

第一行，两个正整数 L 和 R。
输特殊式

一行，一个整数，表现区间中素数的个数。
输入输出样例

输入 #1复制

2. 2 11

复制代码

输出 #1复制

2. 5

复制代码

代码实现：
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1e6 + 1;
// 标记数组，用于标记每个数是否为质数
vector<bool> isPrime(MAX, true);
// 利用埃拉托斯特尼筛法筛选质数
void sieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAX; ++i) {
        if (isPrime) {
            for (int j = i * i; j < MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }
}
int main() {
    int n, k;
    cin >> n >> k;
    // 查抄输入的公道性
    if (n > k) {
        cout << "输入错误：n 不能大于 k。" << endl;
        return 1;
    }
    // 初始化筛法
    sieve();
    int count = 0;
    // 统计区间 [n, k] 内质数的个数
    for (int i = n; i <= k; ++i) {
        if (isPrime) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}