闲来无事稍稍复习了一下筛法
素数这玩意大家都应该不陌生,常规的判断素数的方法应该都会。只不过,常规的方式仅仅只是判断一个数是否为素数,如果判断出0~n中所有的素数,常规方式的时间复杂度就比较高了。
所以大佬们搞出了好多大佬方法,我习惯统称为素数筛(其实应该叫筛法)。
PS: 这期的代码会用 C++
和 Python
写
先来常规方法趴
常规方式,就是判定n是否是素数,就是循环2~n-1,判断是否整除
这里写的比较完整点,下面小于2的判断就不打了
if(n<2)return printf("%d<2,不予判断",n); |
import math |
代码是一样的,只是我现在是在学 python
,所以我会打个 python
的版本出来(由于 python
本身的原因,速度会比 C++
慢)
当然,如果只是判断一个数,以上的常规做法就足够使用了,但如果是多个数,就需要弄出一个素数表了
(如果用上面方法进行 2 ~ N 的筛查,时间复杂度为O(n^2)
筛法
PS:以下代码是求 1 ~ N 的素数
众所周知,合数的定义说明它有除 1 和本身外的因子
那么,合数是质数或合数的倍数了,也就可以通过筛除当前数的小于n的倍数来解决许多合数
下面讲解的三种算法中,都用了这样一个原理:
如果当前的数没有被筛出,显然它不是前面任意数的倍数,那它实锤素数了,把他记进小本本
朴素筛
为什么朴素呢,这个方法确实简单直白
时间复杂度为O(nlogn)
int prime[1001]; |
prime=[] |
埃氏筛
全称 ‘’埃拉托斯特尼筛法’’,好家伙,他发现上面那个朴素筛干了一件不太好的事
明明一个合数都可以分解质因数了,为什么要合数筛合数啊,全用素数筛它不香吗?
于是许多数字不需要被筛它的(因素个数)遍了
这大大节省了好多时间啊
于是优秀的埃氏筛时间复杂度为O(nloglogn),emmm,针不戳!
int prime[1001]; |
prime=[] |
于是程序员们发现,这,这不就把最内层的 for 放到了 if 里面?
啊这,这埃拉托斯特尼就这样名垂千古了?
不过说实在效率确实提升了挺多(已经很接近O(n)了)
线性筛
这个就很 nb 了,它还有另外一个名字:”欧拉筛法” (居然百度百科查不到)
上面两种筛法都有一个缺点,就是一个合数可能会被多个数重复筛出
例如朴素筛中,100会重复被2,4,5,10,20,25,50筛出,而在埃氏筛中,100只会被2和5筛出
而在埃氏筛中,30会被2,3,5筛出
埃氏筛只解决了一部分问题,剩余的线性筛就出来干活了
一个合数只会经过一次筛选,它的核心在于
只被该合数最小的质因数筛出
那么,如何实现这个算法?
假设 a 是合数 n 的最小质因数,那么 n = i * (n / i)
i 和 n / i 一定小于 n ,i 已经在 2 ~ n 的素数表里了,所以我们要做的就是在循环到 n / i 时把 n 筛出
为了更好地理解,我去爬了张图:
从图上我们看到,第一列筛掉的是最小素因子是 2 的数,第二列筛掉的是最小素因子为 3 的数,依次类推,可以把所有的合数都筛掉。
因为是按照最小素因子筛选,每个数的最小素因数只有一个,所以可以保证每个数都只会被筛一遍。
例如, i = 6 时,第一个素数是 2 ,能整除,筛掉 12 后就break;至于第二个素数 3 , 6 x 3 中的最小素因数肯定是前一个素数 2 ,所以它要到 i = 9 ,素数取 2 时才被筛掉。
欧拉筛的速度大概是埃氏的 3 - 4 倍,然而在小数据中却有被完爆的可能(因为埃氏筛cache友好?)。
线性筛的时间复杂度就十分优秀了,为O(n)
int prime[1001]; |
prime=[] |
线性筛在超量数据面前的效率是非常高的
只是线性筛这个做法比较难以理解
好累啊,打这一篇写了一个中午,困死了,睡了睡了
(在图书馆下午2点多睡觉就很迷)