素数密度

题意

统计 [L,R] 中素数个数。R 接近 2^31，但区间长度不超过 10^6。

思路

不能筛到 R。任何区间合数都至少有一个不超过 sqrt(R) 的质因子：

普通埃氏筛得到 2..sqrt(R) 的素数；
建立长度 R-L+1 的区间标记；
对每个基础素数 p，从 max(p*p,ceil(L/p)*p) 开始标记倍数；
若 L=1，单独把 1 标为非素数。

从 p*p 开始可避免把区间中的质数 p 自己误删。

Python 知识

bytearray 适合百万长度 0/1 标记。
扩展切片赋值一次标记同一质数的全部倍数。
(left+p-1)//p*p 是不小于 left 的第一个 p 倍数。
sum(segment) 直接统计仍为 1 的位置。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：紧凑标记和切片性能。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：区间按需处理思路。

代码

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
30import sys


def main():
    left, right = map(int, sys.stdin.buffer.read().split())
    limit = int(right ** 0.5)
    base_prime = bytearray(b"\x01") * (limit + 1)
    if limit >= 0:
        base_prime[0] = 0
    if limit >= 1:
        base_prime[1] = 0
    for prime in range(2, int(limit ** 0.5) + 1):
        if base_prime[prime]:
            start = prime * prime
            base_prime[start::prime] = b"\x00" * ((limit - start) // prime + 1)

    segment = bytearray(b"\x01") * (right - left + 1)
    for prime in range(2, limit + 1):
        if not base_prime[prime]:
            continue
        start = max(prime * prime, (left + prime - 1) // prime * prime)
        if start <= right:
            segment[start - left::prime] = b"\x00" * ((right - start) // prime + 1)
    if left == 1:
        segment[0] = 0
    print(sum(segment))


if __name__ == "__main__":
    main()

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/**
 * P1835 素数密度
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 50000; // sqrt(2^31) ≈ 46340
const int MAXL = 1000005;

bool is_prime[MAXV + 5]; // 小范围内筛素数
int primes[MAXV], pcnt;
bool seg[MAXL]; // 区间 [l,r] 的素数标记

int main() {
    int l, r;
    scanf("%d%d", &l, &r);
    // 小范围素数筛
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= MAXV; ++i) {
        if (is_prime[i]) {
            primes[++pcnt] = i;
            if ((long long)i * i <= MAXV) {
                for (int j = i * i; j <= MAXV; j += i)
                    is_prime[j] = false;
            }
        }
    }
    // 大区间筛
    for (int i = 1; i <= pcnt; ++i) {
        int p = primes[i];
        long long start = max(1LL * p * p, (l + p - 1LL) / p * p);
        for (long long j = start; j <= r; j += p)
            seg[j - l] = true;
    }
    if (l == 1) seg[0] = true;
    int ans = 0;
    for (int i = 0; i <= r - l; ++i)
        if (!seg[i]) ++ans;
    printf("%d\n", ans);
    return 0;
}

复杂度

基础筛和区间标记约 $O(\sqrt R\log\log R+(R-L+1)\log\log R)$ ，空间 $O(\sqrt R+R-L+1)$ 。

总结

数值上界大但查询区间短，是分段筛的典型信号：只为当前区间分配标记。

目录

题意

思路

Python 知识

代码

复杂度

总结