题目描述

给定区间 [L, R]（1 ≤ L ≤ R < 2^31，R - L ≤ 1e6），请计算区间中素数的个数。

输入格式

第一行，两个正整数 L 和 R。

输出格式

一行，一个整数，表示区间中素数的个数。

样例 #1

样例输入 #1

2 11

样例输出 #1

5

题解

参考 https://blog.integral.org.cn/archives/luogup3912 的解法

埃氏筛优化版

如果直接用埃氏筛求解，由于 R 的最大值可逼近 2^31，会导致数组过大超出内存限制（本题内存限制 128M）。
思考这样一个性质：

• 一个合数 n 的最小质因子一定小于 sqrt(n)（即合数 n 一定能被小于 sqrt(n)的素数筛出）

因此，我们只需要先生成 [2, sqrt(r)] 范围内的所有素数，然后用这些素数去筛 [L, R] 范围内的数。
代码如下：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define PRIME 0
#define NOT_PRIME 1
#define PRIME_SIZE 40000

int main() {
  int l, r, i, j;
  long long k;
  scanf("%d %d", &l, &r);
  /*
    isPrime 数组用来存放前 sqrt(r) 的数是否为素数的信息
    prime 数组用来存放小于等于 sqrt(r) 的所有素数
    注意 1 不是素数需要特殊处理
    从一共 r - l + 1 个数中剔除所有合数
  */
  _Bool *isPrime = (_Bool *)calloc(sqrt(r), sizeof(_Bool));
  int prime[PRIME_SIZE];
  *isPrime = NOT_PRIME;
  int count = r - l + 1;

  for (i = 2; i <= sqrt(sqrt(r)); i++)
    if (isPrime[i - 1] == PRIME)
      for (j = i * i; j <= sqrt(r); j += i)
        isPrime[j - 1] |= NOT_PRIME;

  j = 0;
  for (i = 2; i <= sqrt(r); i++)
    if (isPrime[i - 1] == PRIME)
      prime[j++] = i; // 生成素数表
  /*
    primeNum 用来存放小于等于 sqrt(r) 的素数的个数
    isPrimeFinal 数组用来存放 [l, r] 中的数是否为素数的信息
    注意把区间 [l, r] 转化为 [1, r - l + 1]
    （索引号从 0 到 r - l）
    1 不是素数需要特殊判断
  */
  const int primeNum = j;
  _Bool *isPrimeFinal = (_Bool *)calloc(r - l + 1, sizeof(_Bool));
  if (l == 1)
    *isPrimeFinal = NOT_PRIME;

  // k 的初值是大于等于 l 的 prime[i] 的倍数的最小值
  for (i = 0; i < primeNum; i++)
    for (k = ((l - 1) / prime[i] + 1) * prime[i]; k <= r; k += prime[i])
      isPrimeFinal[k - l] |= NOT_PRIME;

  for (i = 0; i <= r - l; i++)
    count -= isPrimeFinal[i];

  printf("%d", count);
  free(isPrime);
  free(isPrimeFinal);
  return 0;
}