算法
(枚举约数) $O(q)$
先用线性筛统计出 $2 \sim 10^5$ 中的所有质数,然后再用前缀和来统计前 $i$ 个 像2017
的数的个数。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
const int N = 100005;
int primes[N], cnt;
bool st[N];
void get_primes(int n) {
for (int i = 2; i <= n; ++i) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; ++j) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int c[N];
void init(int n) {
get_primes(n);
for (int i = 3; i <= n; ++i) {
c[i] += c[i - 1] + (!st[i] and !st[(i + 1) / 2]);
}
}
int main() {
init(N);
int q;
cin >> q;
rep(qi, q) {
int l, r;
cin >> l >> r;
int ans = c[r] - c[l - 1];
cout << ans << '\n';
}
return 0;
}