【算法与数据结构】——素数筛

我会带着你远行 2022-10-16 08:45 131阅读 0赞

素数筛是比较常用的基础知识，通常穿插在题目中，作为题解的一部分。  
作简单记录，给自己看。

## 埃氏筛 ##

埃拉托斯特尼筛法，简称埃氏筛。

学习埃氏筛之前，我们先看一下暴力筛法，即对每个数都用试除法判断其是不是质数：

暴力筛法：

# N = 1e7 + 5;
    int st[N]; // 初始化为0， 0表示质数，1表示合数
    
    for(int i = 2; i <= n; i++){
    	for(int j = 2; j <= i / j; j++){//试除法
    		if(i % j == 0){
    			st[i] = 1; // 合数，标记为1 
    		}
    	}
    }

这种方式无疑是最慢的，我们看一下如何加快，换一种思路：一个质数的倍数一定是合数  
埃氏筛的思想就是基于此，将一个集合内的所有质数的倍数全部删去，留下的就是质数。  
因为一个合数一定能被分解为几个质数的幂的乘积，并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。  
埃氏筛代码：

#define N 1e7 + 5;
    int st[N];
    public static void E_sieve(int  n){
    
    	for(int i = 2; i <= n; i++)
    	{
    		if(st[i] == 0)
    		{
    			for(int j = 2 * i; j <= n; j += i)
    			    st[j] = 1; // j是i的一个倍数，j是合数，筛掉。
    		}
    	}
    	
    }

我们还可以对其进行优化：

1.  我们会先筛2的所有倍数，然后筛3的所有倍数，但筛除3的倍数时，我们还是从3的2倍开始筛，其实3 \* 2 ，已经被2 \* 3时筛过了。所以我们每一次只需要从i\*i开始筛，因为(2，3,…,i - 1)倍已经被筛过了。
2.  另外，判断一个数n是不是质数，我们只判断\[ 2 ,  n \\sqrt\{n\} n \]内有没有它的因子。在筛合数的时候，我们也可以这样做，因为一个合数的最小质因子一定小于等于 n \\sqrt\{n\} n。  
    所以对于区间 \[ 1 , 1 e 7 \] \[1, 1e7\] \[1,1e7\]，最大的合数是 1 e 7 1e7 1e7, 它的最小质因子一定是小于等于 1 e 7 \\sqrt\{1e7\} 1e7  
    ，区间内其他的合数的最小质因子也一定是小于等于 1 e 7 \\sqrt\{1e7\} 1e7的，所以只需要用 \[ 1 , 1 e 7 \] \[1,\\sqrt\{1e7\}\] \[1,1e7\]中的质数就可以筛去 \[ 1 , 1 e 7 \] \[1, 1e7\] \[1,1e7\]中所有的合数。  
    优化后的埃氏筛:

#define N  1e7 + 5;
    int isPrime[N];
    void E_sieve(int  n){
    	for(int i = 2; i <= n / i; i++)
    	{
    		if(isPrime[i] == 0)
    		{
    			for(int j = i * i; j <= n; j += i)
    			    isPrime[j] = 1; // j是i的一个倍数，j是合数，筛掉。
    		}
    	}
    }

优化后的时间复杂度可以近似看成O ( n ) O(n)O(n)了。  
但是，我们还可以更快，那就是欧拉筛。

## 欧拉筛 ##

欧拉筛，又称为线性筛，时间复杂度为O ( n ) O(n)O(n)。  
代码：

#define N 1e7 + 5;
    int isPrime[N];
    int primes[N];
    void ola(int n)
    {
        for (int i = 2; i <= n; i ++ )
        {
            if (isPrime[i] == 0) primes[cnt ++ ] = i;//将质数存到primes中
            for (int j = 0; primes[j] <= n / i; j ++ )//要确保质数的第i倍是小于等于n的。
            {
                isPrime[primes[j] * i] = 1;
                if (i % primes[j] == 0) break;
            }
        }
    }

埃氏筛是筛去每个质数的倍数，但难免，会有合数会被其不同的质因子多次重复筛去。这就造成了时间浪费。

比如说：  120 = 2 3 ∗ 3 ∗ 5 120 = 2^3 ∗ 3 ∗ 5 120=23∗3∗5  
120 会被2筛去一次， 3筛去一次， 5筛去一次。  
多做了两次不必要的操作。  
因此欧拉筛要解决的关键问题就是确保一个数只被筛一次。  
我们不需要用一个for循环去筛除一个质数的所有倍数，我们将所有质数存储到 p r i m e s \[ \] primes\[\] primes\[\]中，然后枚举到第i个数时，就筛去所有的 p r i m e s \[ j \] ∗ i primes\[j\] \* i primes\[j\]∗i。这样就在每一次遍历中，正好筛除了所有已知素数的i倍。  
如果 i % p r i m e s \[ j \] = = 0 i \\% primes\[ j \] == 0 i%primes\[j\]==0, 我们就结束内层循环。否则就会导致一个数被重复删除。  
具体原因可以参考[素数筛法详解：埃氏筛和欧拉筛][Link 1]

[Link 1]: https://blog.csdn.net/GD_ONE/article/details/104660294