跳至正文

1 条题解

  • 0
    @ 2026-10-8 19:19:22

    【本题解由站长编写】

    统计区间 [L,R] 内素数个数,R 最大到 2^31-1,直接筛到 R 会爆内存——但题目保证 R-L ≤ 10^6,所以用分段筛:先筛出 √R 以内的所有素数(√(2^31) ≈ 46341,数组开得下),再用它们去筛 [L,R] 区间内每个数的倍数。对每个素数 p,从 max(p*p, ceil(L/p)*p) 开始标记,因为小于 p*p 的 p 的倍数已被更小的素数筛掉。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        long long L, R;
        cin >> L >> R;
        int limit = (int)sqrt((long double)R) + 1;
        vector<char> small(limit + 1, 0);
        vector<int> primes;
        for (int i = 2; i <= limit; i++) {
            if (small[i]) continue;
            primes.push_back(i);
            for (long long j = (long long)i * i; j <= limit; j += i) small[j] = 1;
        }
    
        long long len = R - L + 1;
        vector<char> isPrime(len, 1);
        if (L <= 0 && len > 0) isPrime[0] = 0;
        if (L <= 1 && len > 1) isPrime[1] = 0;
    
        for (int p : primes) {
            long long start = max((long long)p * p, ((L + p - 1) / p) * (long long)p);
            for (long long x = start; x <= R; x += p) isPrime[x - L] = 0;
        }
    
        long long cnt = 0;
        for (long long i = 0; i < len; i++) if (isPrime[i]) cnt++;
        cout << cnt << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4178
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者