517编程普及组数学之筛法
![](https://image.wsq127.top/file/c77b717f9f211d6a3607c.png)
517编程普及组数学之筛法
wsq127作用:筛法可以求出 $[1,n]$ 的所有素数
埃氏筛
埃拉托斯特尼筛法,简称埃氏筛是求解素数的一种经典方法,和辗转相减一样古老,最初由古希腊数学家埃拉托斯特尼(Eratosthenes)提出。
我们发现对于任意一个正整数,他的所有倍数一定都是合数。
有了这个理论,我们便可以写出最朴素的筛法,复杂度 $O(n\log n)$。
1 | void sieve() |
埃氏筛(优化)
对于上面这个版本,我们发现 $21$ 会被 $3$ 和 $7$ 筛两遍,大大浪费了时间。
针对这种情况,我们可以只枚举较小的因子,也就是说只用小于 $\sqrt[2]n$ 的数去筛,转化为因子的角度就是只去筛大于等于 $x^2$ 的数。
代码变动不大,虽然渐进复杂度仍然是 $O(n\log n)$,不过常数得到了优化:
1 | void sieve() |
欧拉筛
欧拉筛由著名的古希腊数学家欧拉(Euler)提出,他是18世纪著名的数学家和物理学家,被认为是现代数学的奠基人之一。
在欧拉时代,素数的研究已经有了相当长的历史。埃拉托斯特尼筛法虽然在古代就已经被提出,但随着数学研究的深入,人们开始意识到埃拉托斯特尼筛法的局限性,尤其是在大数值范围内的应用。因此,人们迫切需要一种更高效的素数筛法。
实现
欧拉筛可以实现 $O(n)$ 复杂度,也就是线性筛。
观察到在埃氏筛中,经过优化后仍会出现同一个数可能被多个素数重复筛掉,比如 $30$ 会被 $2,3,5$ 重复筛掉。
为了解决这一问题,我们可以让合数只被它的最小质因数筛掉
先放上代码:
1 | void sieve() |
虽然不是很长,但是十分玄学。
证明
首先说一下 if(i%prm[j]==0) break;
的作用:
- 如果没有这一句,每一个素数会筛掉所有与大于等于它本身的数相乘得到的数,而我们只需要用最小质因数去筛。
再讲一下加上他后为何仍然正确(((:
- 假设我们要筛掉合数 $a$,$a$ 的最小质因数是 $p$,令 $a=pb$。
- 显然 $a>b$,
- 因为 $p$ 是最小质因数,所以 $p\le b$,
- 这样就能保证在用 $b$ 筛掉 $a$ 之前不会
break
掉。
评论
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果