闲来无事稍稍复习了一下筛法

素数这玩意大家都应该不陌生,常规的判断素数的方法应该都会。只不过,常规的方式仅仅只是判断一个数是否为素数,如果判断出0~n中所有的素数,常规方式的时间复杂度就比较高了。

所以大佬们搞出了好多大佬方法,我习惯统称为素数筛(其实应该叫筛法)。

PS: 这期的代码会用 C++Python


先来常规方法趴

常规方式,就是判定n是否是素数,就是循环2~n-1,判断是否整除

这里写的比较完整点,下面小于2的判断就不打了

1
2
3
4
5
6
7
8
9
if(n<2)return printf("%d<2,不予判断",n); 
bool isprime=true;
for(int i=2;i<n;i++)
if(n%i==0){
isprime=false;
break;
}
if(isprime)cout<<n<<"为素数"<<endl;
else cout<<n<<"为合数"<<endl;
1
2
3
4
5
6
7
8
import math
isprime=True
for i in range(2,int(math.sqrt(n))+1):
if n%i==0:
isprime=False
break
if isprime:print("{}为素数".format(n))
else:print("{}为合数".format(n))

代码是一样的,只是我现在是在学 python ,所以我会打个 python 的版本出来(由于 python 本身的原因,速度会比 C++ 慢)

当然,如果只是判断一个数,以上的常规做法就足够使用了,但如果是多个数,就需要弄出一个素数表了

(如果用上面方法进行 2 ~ N 的筛查,时间复杂度为O(n^2)



筛法

PS:以下代码是求 1 ~ N 的素数

众所周知,合数的定义说明它有除 1 和本身外的因子

那么,合数是质数或合数的倍数了,也就可以通过筛除当前数的小于n的倍数来解决许多合数

下面讲解的三种算法中,都用了这样一个原理:

如果当前的数没有被筛出,显然它不是前面任意数的倍数,那它实锤素数了,把他记进小本本


朴素筛

为什么朴素呢,这个方法确实简单直白

时间复杂度为O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int prime[1001];
bool st[1001]; // 假设都是素数吧(true为合数)

// 朴素筛
void get_prime(int n){
for(int i=2;i<=n;i++){
if(!st[i])prime[++prime[0]]=i;
for(int j=i*i;j<=n;j+=i)st[j]=true; // 不管是合数还是质数,都用来筛掉后面它的倍数
}
}

int main(){
st[0]=true,st[1]=true; // 先把0和1筛掉
get_prime(1000);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
prime=[]
st=[False for i in range(0,1001)] # 假设都是素数吧(True为合数)
st[0]=True
st[1]=True
# 先把0和1筛掉

# 朴素筛
def get_prime(N):
for i in range(2,N+1):
if st[i]==False:
prime.append(i)
for j in range(i*i,N+1,i): # 不管是合数还是质数,都用来筛掉后面它的倍数
st[j]=True

get_prime(1000)

埃氏筛

全称 ‘’埃拉托斯特尼筛法’’,好家伙,他发现上面那个朴素筛干了一件不太好的事

明明一个合数都可以分解质因数了,为什么要合数筛合数啊,全用素数筛它不香吗?

于是许多数字不需要被筛它的(因素个数)遍了

这大大节省了好多时间啊

于是优秀的埃氏筛时间复杂度为O(nloglogn),emmm,针不戳!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int prime[1001];
bool st[1001]; // 假设都是素数吧(true为合数)

// 埃氏筛
void get_prime(int n){
for(int i=2;i<=n;i++){
if(!st[i]){
prime[++prime[0]]=i;
for(int j=i*i;j<=n;j+=i)st[j]=true; // 可以用质数就把所有的合数都筛掉
}
}
}

int main(){
st[0]=true,st[1]=true; // 先把0和1筛掉
get_prime(1000);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
prime=[]
st=[False for i in range(0,1001)] # 假设都是素数吧(true为合数)
st[0]=True
st[1]=True
# 先把0和1筛掉

# 埃氏筛
def get_prime(N):
for i in range(2,N+1):
if st[i]==False:
prime.append(i)
for j in range(i*i,N+1,i): # 可以用质数就把所有的合数都筛掉
st[j]=True

get_prime(1000)

于是程序员们发现,这,这不就把最内层的 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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int prime[1001];
bool isprime[1001]; // 假设都是素数吧(true为合数)

// 线性筛
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!isprime[i])prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&i*prime[j]<=n;++j) // 对于任意一个合数x,假设pj为x最小质因子,当i<x/pj时,一定会被筛掉
{
isprime[i*prime[j]]=true;
if(i%prime[j]==0)break;
// 1.i%pj==0, pj定为i最小质因子,pj也定为pj*i最小质因子
// 2.i%pj!=0, pj定小于i的所有质因子,所以pj也为pj*i最小质因子
}
}
}

int main()
{
isprime[0]=true,isprime[1]=true; // 先把0和1筛掉
get_prime(100);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
prime=[]
st=[False for i in range(0,1001)] # 假设都是素数吧(true为合数)
st[0]=True
st[1]=True
# 先把0和1筛掉

# 线性筛
def get_prime(N):
for i in range(2,N+1):
if st[i]==False:
prime.append(i)
for pj in prime: # 对于任意一个合数x,假设pj为x最小质因子,当i<x/pj时,一定会被筛掉
if pj*i>N:break
st[pj*i]=True
if i%pj==0:
break
# 1.i%pj==0, pj定为i最小质因子,pj也定为pj*i最小质因子
# 2.i%pj!=0, pj定小于i的所有质因子,所以pj也为pj*i最小质因子

get_prime(1000)

线性筛在超量数据面前的效率是非常高的

只是线性筛这个做法比较难以理解


好累啊,打这一篇写了一个中午,困死了,睡了睡了

(在图书馆下午2点多睡觉就很迷)