1 条题解
-
0
【本题解由站长编写】
统计区间 [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
- 上传者