判决素数个数

题目描述

输入两个整数 $X$ 和 $Y$ （ $1 \le X, Y \le 10^5$ ），输出两者之间的素数个数（包括 $X$ 和 $Y$ ）。不保证 $X \le Y$ 。

样例输入

text

11 100

样例输出

text

思路

值域固定为 $10^5$ ，用埃氏筛一次性预处理素数表，再把区间 $[\min(X,Y), \max(X,Y)]$ 内的素数个数求和即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-06 10:30
# update_at: 2026-07-06 10:30

import sys

LIMIT = 10**5  # 题面保证 X, Y <= 10^5


def sieve_primes(limit: int) -> list[bool]:
    """埃氏筛：is_prime[n] 表示 n 是否为素数。"""
    is_prime = [True] * (limit + 1)
    is_prime[:2] = [False, False]                     # 0 和 1 不是素数
    for n in range(2, int(limit**0.5) + 1):
        if is_prime[n]:
            is_prime[n * n :: n] = [False] * len(is_prime[n * n :: n])
    return is_prime


def solve() -> None:
    x, y = map(int, sys.stdin.buffer.read().split())  # 两数无大小顺序，统一成闭区间 [lo, hi]
    lo, hi = min(x, y), max(x, y)

    is_prime = sieve_primes(LIMIT)
    print(sum(is_prime[lo : hi + 1]))                 # 前缀和相减也可以，这里直接区间求和


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:10
 * update_at: 2026-10-05 23:10
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int LIMIT = 100000; // 题目值域上限

bool is_prime[LIMIT + 1]; // is_prime[i] = true 表示 i 是素数

// 埃氏筛预处理 2~LIMIT 的素数表
void sieve() {
    for (int i = 2; i <= LIMIT; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数
    for (int i = 2; i * i <= LIMIT; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= LIMIT; j += i)
                is_prime[j] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieve();

    int x, y;
    cin >> x >> y;
    int lo = min(x, y);
    int hi = max(x, y);

    int ans = 0;
    for (int i = lo; i <= hi; i++)
        if (is_prime[i]) ans++;

    cout << ans << "\n";
    return 0;
}

目录

题目描述

思路

参考代码