洛谷P1835 素数密度(分段筛的思想)

题目描述

给定 $L,R$，请计算区间 $[L,R]$ 中素数的个数。

$1\le L\le R<2^{31}$，$R-L\le 10^6$。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

2 11

输出 #1

5

提交链接

素数密度

思路分析

R 的上限接近 $2^{31}$，数量级为 $10^9$ ，因此不能对整个区间直接进行素数筛。

引入：

合数：是指大于 $1$ 且不是素数的数，也就是说它可以表示成两个大于 $1$ 的整数的乘积。

<=> $x=a\times b$，其中 $1<a\le b<x$ ----> $a\le \sqrt{x}$ 或 $b\le \sqrt{x}$

考虑最大范围，每个合数 $x$ 至少有一个因数 $\le \sqrt{R}$。并且这个因子一定为素数(要么是素数，要么能进一步分解成素数(唯一分解定理))

得到：

1. 埃氏筛预处理 $[1,1e5]$ 范围内的素数。

   const int maxn = 1e5;
   typedef long long LL;
   bool is_prime[maxn + 9];
   vector<long long> p;is_prime[0] = is_prime[1] = true;for (LL i = 2; i <= maxn; i++)
   {if (!is_prime[i]){p.push_back(i);for (LL j = i * i; j <= maxn; j += i)is_prime[j] = true;}
   }
   

2. 每一个素数 $p$ ,标记处于 $[L,R]$ 范围内的倍数。（埃氏筛思想）

   找到素数 $p$ 在 $[L,R]$ 中的第一个倍数，然后从那开始每隔 $p$ 个数筛掉一次。

   起始位置： strat = strat = max(p * p, (L + p - 1) / p * p);

3. 利用 $R-L\le 10^6$ 的关系，引入小范围的标记数组。

   $R$ 可能高达 $2^{31}$，我们不能直接开一个大小为 $R+1$ 的数组，内存根本放不下。

   引入：bool check[1000009];

   $check[i]$ 表示 $L+i$ 是否为素数(（对原始区间 $[L,R]$的“映射”）

4. 特殊情况处理。

   当 $L=1$ 时，数值 $1$ 本身不会被任何素数筛掉，必须手动将其标记为非素数。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
typedef long long LL;
bool is_prime[maxn + 9], check[1000009];
vector<long long> p;void init() // 埃氏筛  预处理1e5范围内的素数
{is_prime[0] = is_prime[1] = true;for (LL i = 2; i <= maxn; i++){if (!is_prime[i]){p.push_back(i);for (LL j = i * i; j <= maxn; j += i)is_prime[j] = true;}}
}int main()
{init();LL l, r;cin >> l >> r;for (int i = 0; i < p.size(); i++) // 每一个素数去筛[l,r]范围内的非素数{LL x = max(p[i] * p[i], (l + p[i] - 1) / p[i] * p[i]); // 起始位置for (LL j = x; j <= r; j += p[i])check[j - l] = true; // 映射}if (l == 1)check[0] = true;   //特殊情况处理int cnt = 0;for (int i = l; i <= r; i++){if (!check[i - l])cnt++;}cout << cnt;return 0;
}