P1835. 素数密度

发表于 分类于 阅读次数： Waline： 本文字数： 205 阅读时长 ≈ 1 分钟

考点

  • 区间筛

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LEN = 1e6 + 50;
bitset<LEN> vis;
int tot, pri[LEN];

void f(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) pri[++tot] = i;
    for (int j = 1; j <= tot && 1ll * i * pri[j] <= n; ++j) {
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) break;
    }
  }
  vis.reset();
}

int main() {
  f(1 << 16);  // 线性筛2^16以内的质数
  ll l, r;
  cin >> l >> r;
  for (int i = 1; i <= tot; ++i) {
    // 埃氏筛的思想，筛掉[l,r]范围内的pri[i]的倍数
    // 至少是2倍，总不能把自己也筛了吧-。-
    for (ll j = max(2ll, (l - 1) / pri[i] + 1) * pri[i]; j <= r; j += pri[i]) {
      vis[j - l] = 1;
    }
  }
  int ans = 0;
  // 左边界l至少为2，因为0和1不是质数
  for (int i = max(2ll, l); i <= r; ++i) {
    if (!vis[i - l]) ++ans;
  }
  cout << ans;
  return 0;
}

思路

直接上《深基》的图