素数个数

题目描述

求 $2 \sim n$ （ $2 \leqslant n \leqslant 50000$ ）中素数的个数。输入一行整数 $n$ ，输出素数个数。样例输入 10，对应输出 4。

思路

埃拉托斯特尼筛：从小到大枚举素数 $p$ ，把 $p^2, p^2+p, \dots$ 全部标记为合数。筛完后 $[2, n]$ 中未被标记的数就是素数，统计个数即可。

参考代码

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-07 10:00
# update_at: 2026-07-07 10:00

import sys


def sieve_count(n: int) -> int:
    """埃拉托斯特尼筛：返回 [2, n] 中素数个数。"""
    if n < 2:
        return 0
    is_prime = bytearray(b"\x01") * (n + 1)   # 1 表示待判定为素数
    is_prime[0:2] = b"\x00\x00"               # 0 和 1 不是素数
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            step = p
            start = p * p
            is_prime[start:n + 1:step] = b"\x00" * ((n - start) // step + 1)
    return is_prime.count(1)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    print(sieve_count(n))


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/**
 * 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 03:32
 * update_at: 2026-10-05 03:32
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 50005;

bool is_composite[MAXN]; // is_composite[i] 为 true 表示 i 已被筛掉，是合数

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

    ll n;
    cin >> n;

    // 埃拉托斯特尼筛：从小到大枚举素数 p，把 p*p, p*p+p, ... 标记为合数
    for (ll p = 2; p * p <= n; p++) {
        if (is_composite[p]) {
            continue;
        }
        for (ll j = p * p; j <= n; j += p) {
            is_composite[j] = true;
        }
    }

    // 统计 [2, n] 中未被标记的数的个数，即素数个数
    ll answer = 0;
    for (ll i = 2; i <= n; i++) {
        if (!is_composite[i]) {
            answer++;
        }
    }

    cout << answer << endl;

    return 0;
}

目录

题目描述

思路

参考代码