质数筛
拔丝地瓜
  2022-06-06 10:15:44 2022-06-06 10:15    

质数筛

埃氏筛

素数筛法，是一种快速“筛”出​​之间所有素数的方法。

朴素的筛法叫埃氏筛（the Sieve of Eratosthenes，埃拉托色尼筛），它的过程是这样的：

先将​​​​的数按顺序写出来：

从前往后看，找到第一个未被划掉的数，是2，说明它是质数（这里是质数用标为蓝色表示）。然后把2的倍数（不包括2）划掉（这里划掉用标红表示）：


下一个未被划掉的数是3，它是质数，然后把3的倍数划掉：

接下来应该是5，但是由于5已经超过​了，所以遍历结束，剩下未被划掉的都是素数：

这个过程用代码表示为：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPrime[MAXN+5] = {0};//标记数组 用来表示数字是否是质数：true表示是质数，false表示不是质数

void aiPrime(int n){//埃氏筛处理n以内的质数
	memset(isPrime,true,sizeof(isPrime));//所有数字，默认标记为质数 
	isPrime[1] = false;//修改1的状态，1不是质数
	for(int i = 2; i * i <= n; i++){//从2开始，枚举范围n以内的每个数字 
		if(isPrime[i]){//如果i是质数，则将n以内所有i的倍数（2倍及以上），标记为非质数 
			for(int j = 2; j * i <= n; j++){
				isPrime[j*i]=false;// 标记i的倍数为非质数 
			}
		}
	}
}

埃式筛算法的复杂度是 ​​，但是我们发现，在筛的过程中我们会重复筛到同一个数，例如12同时被2和3筛到，30同时被2、3和5筛到。

所以我们引入欧拉筛，也叫线性筛，可以在​时间内完成对的筛选。它的核心思想是：让每一个合数被其最小质因数筛到。

欧拉筛

这次除了要把​列出来，还维护一个质数表：

仍然是从头到尾遍历，第一个数是2，未被划掉，把它放进质数表：

然后用2去乘质数表里的每个数，并且划掉它们：

下一个是3，加入质数表，并用3去乘质数表里每一个数（此时是2和3），划掉6和9：

下一个是4（注意：这里划掉的数也要遍历，只是不加入质数表），用4去乘质数表里每个数，划掉8，但不划掉12，因为​​，应该由它的最小质因数2筛掉，而不是3。

实际上，对于数​，当遍历到质数表中的 ​ ，且发现 ​​（能整除）时，就应当停止遍历质数表。

因为如果​​​​​​，即i%p == 0​，则说明

假设在质数表中​​​​的下一位是​​​​​，设

所以由有，因为，设所以​​​​​，则

所以如果用​​式筛掉所以如果用3式筛去​​的话，当​​时，​​又会被​​​式筛去一次，为了确保合数只被最小质因子筛掉，最小质因子要乘以最大的倍数，即要乘以最大的​​, 所以不能提前筛。

下一个数是5，加入质数表，划掉10和15：

下一个数是6，划掉12，6能被2整除，跳过。

……

按这样的步骤进行下去，可以筛掉所有的合数，并得到一张质数表：

我们可以保证每个合数都被筛过。设任意合数 ，其中是的最小质因数，又设，是的最小质因数。在处理时时，要遍历质数表，直到遇到时才结束，所以任意小于等于的质数与的乘积，都会在此时被筛掉。

而由于一定有（因为的最小质因数是，而不是），所以在处理到时，一定会被筛到。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
bool isPrime[MAXN+5];  
int prime[MAXM+5];  

//判断是否是一个素数  Mark 标记数组 index 素数个数  
void olaPrime(){
    int index = 0;
    memset(isPrime,true,sizeof(isPrime));  
    for(int i = 2; i < MAXSIZE; i++){   
        //如果i未被标记为非素数（即false）则得到一个素数  
        if(isPrime[i] == true){  
            prime[index++] = i;  
        }  
        //标记目前得到的素数的i倍为非素数  
        for(int j = 0; j < index && prime[j] * i < MAXN; j++){   
            isPrime[i * prime[j]] = false;  
            if(i % prime[j] == 0){  
                break;  
            }  
        }  
    }    
}  

//如果空间不够用质数表也可以不用开始就开到最大
bool isnp[MAXN];//is not prime
vector<int> primes; // 质数表
void olaPrime(int n){
    for (int i = 2; i <= n; i++){
        if (!isnp[i]){
            primes.push_back(i);
        }
        for (int p : primes){
            if (p * i > n){
                break;
            }
            isnp[p * i] = 1;
            if (i % p == 0){
                break;
            }
        }
    }
}

欧式筛的时间复杂度为。