素数筛【含算法原理和详细证明】
前置知识:
-
自然数按因数的个数分:质数、合数、$0$、$1$ 四类
-
最小的质数是 $2$,最小的合数是 $4$,连续的两个质数是 $2$、$3$
-
每个合数都可以由几个质数相乘得到,即合数等于质数之积,质数相乘一定得到合数
-
除了 $2$ 和 $5$,其余质数的个位都是 $1、 3、 7、 9$
-
质数定理:当 $n \rightarrow \infty$ 时,$1\sim n$ 中的质数个数为 $\dfrac{n}{\ln n}$。
常用筛法:
1、暴力筛 $O(n\sqrt n)$
通过用判断素数的函数来枚举每一数加入到素数表中。
int primes[N], cnt;
bool is_primes(int n)
{
if (n < 2) return false;
for (int i = 2; i <= n / i; i ++ )
if (n % i == 0)
return false;
return true;
}
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
if (is_prime(i)) primes[cnt ++ ] = i;
}
时间复杂度分析:
遍历 $O(n)$,素数判断最坏 $O(\sqrt n)$,总复杂度为 $O(n\sqrt n)$。
2、朴素筛 $O(n\log n)$
任何整数 $x$ 的倍数 $2x, 3x, \cdots$ 都不可能是素数。我们可以从 $2$ 往后扫描,将当前数的所有倍数全部筛掉,剩下没有被筛掉的数就是质数。
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i ) st[j] = true;
}
}
时间复杂度分析:
当 $i = 2$ 时,第二层循环共循环了 $\dfrac{n}{2}$ 次,$i = 3$ 时循环了 $\dfrac{n}{3}$ 次,$\cdots$,总共循环了: $$\dfrac{n}{2} + \dfrac{n}{3} + \cdots + \dfrac{n}{n} = n(\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n})$$ 其中 $\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n}$ 为调和级数,当 $n \rightarrow \infty$ 时,有:$\sum\limits_{k=1}^{n} \dfrac{1}{k} = \ln n + \gamma$,并且 $\gamma$ 为欧拉常数($\text{Euler Constant}$),约为 $0.577215664\ldots$ 故时间复杂度: $$n(\dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n})\approx n\ln n \approx n\log n$$ 即 $O(n\log n)$。
3、 埃拉托斯特尼(埃氏)筛 $O(n\log \log n)$
对上面的朴素筛法进行优化,我们发现并不需要将每个数的倍数都筛去,我们可以只把所有质数的倍数筛去。
若按照之前的筛法筛去一个整数的所有倍数,我们最终会留下一些质数,以 $p$ 为例,说明 $p$ 不是 $2\sim p - 1$ 内任何一个数的倍数,我们并不需要将 $2\sim p - 1$ 内所有的数依次枚举一遍,只要将其中的质数枚举一遍即可,因为合数等于质数之积。
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
if (!st[i])
{
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i ) st[j] = true;
// for (LL j = (LL)i * i; j <= n; j += i ) st[j] = true;
}
}
这里有个优化,$j$ 可以从 $i\cdot i$ 开始枚举,因为 $i\cdot (2\sim i - 1)$ 已经被 $2\sim i - 1$ 筛去了。但由于数据范围限制,这样会使得 $i\cdot i$ 可能会爆 int
,因此要开 long long
。
时间复杂度分析:
由于我们只用筛去 $2\sim n - 1$ 中的素数倍数即可,故调和级数变为:$\sum\limits_{p\leq n} \dfrac{1}{p}$,其中 $p$ 为质数。当 $n$ 趋于无穷时,有:
$$M = \lim_{n\to \infty} \left (\sum\limits_{p\leq n} \dfrac{1}{p} - \ln(\ln(n))\right) = \gamma + \sum\limits_p \left [\ln \left(1 - \dfrac{1}{p} \right) + \dfrac{1}{p} \right]$$
其中,$M$ 为 $\text{Meissel-Mertens}$ 常数,也称 $\text{Mertens}$ 常数或质数倒数和常数,数值约为 $0.261497\ldots$
所以当 $n\rightarrow \infty$ 时,$n\cdot \sum\limits_{p\leq n} \dfrac{1}{p} \approx n\ln(\ln n)$,即为 $O(n\log \log n)$。
4、 线性(欧拉)筛 $O(n)$
埃氏筛存在一个缺陷,即对于一个合数,可能会被筛多次,例如 $30 = 2\times 15 = 5\times 6\ldots$,我们改用其最小质因子去筛掉这个合数,就可以保证他只会被筛一次。
我们从小到大枚举所有质因子 primes[j]
。
1、当出现 i % primes[j] == 0
时,primes[j]
一定是 $i$ 的最小质因子,因此也一定是 primes[j] * i
的最小质因子。
2、当出现 i % primes[j] != 0
时,说明我们还尚未枚举到 $i$ 的任何一个质因子,也就表示 primes[j]
小于 $i$ 的任何一个质因子,这时 primes[j]
就一定是 primes[j] * i
的最小质因子。
可以发现无论如何,primes[j]
都一定是 primes[j] * i
的最小质因子,并且由于所要筛的质数在 $2\sim n$ 之间,因此合数最大为 $n$,故 primes[j] * i
只需枚举到 $n$ 即可,但由于 primes[j] * i
可能会溢出整数范围,故改成 primes[j] <= n / i
的形式。
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; // primes[j] 一定是 i 的最小质因子
}
}
}
时间复杂度分析:
$2\sim n$ 中,任何一个合数都会被筛去,而且仅用最小质因子去筛,每个合数都有且仅有一个最小质因子,故每个合数只会被筛一次,所以时间复杂度为 $O(n)$。
完整代码:
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
bool st[N];
int primes[N], cnt, n;
void get_primes(int n)
{
...
}
int main()
{
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}
大佬,你这数学符号都是怎么打的
这就是学长的实力吗%%%%%%%
orz 懂了
%%%
清晰,简明扼要
谢谢
%%%