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

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

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

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

先来常规方法趴

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

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

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;

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)

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);
}

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，针不戳！~~

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);
}

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)

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);

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)