【数论算法】素数筛

￡神魔★判官ぃ 2023-10-07 22:54 25阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现
 *   *  2.1.试除法
     *  2.2.埃拉托斯特尼筛法
     *  2.3.欧拉筛法

## 1.概述 ##

（1）在了解素数筛之前，我们先复习一下素数的定义：**素数 (Prime number) 又称质数，一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数 (Composite number)，并且规定 1 既不是质数也不是合数**。

（2）**素数筛**指将一堆数中的合数筛出掉，留下素数的一个过程。求某个大小范围内（例如 2 ~ n）的素数个数，是用到素数筛的最基础的问题，下面将以该问题为切入点，来具体介绍几种常见素数筛算法：试除法、埃拉托斯特尼筛法、欧拉法。

## 2.代码实现 ##

### 2.1.试除法 ###

（1）试除法是根据**素数的定义**而设计的算法，正如字面意思一样，尝试相除。要判断 n 是否为素数，则判断 \[2, sqrt(n)\] 内的整数是否为 n 的因数，即判断 n % i 的值是否为 0，如果为 0，则说明 i 是 n 的因数，故 n 不是素数，返回 false。当判断结束后仍未找到 n 的因数，则说明 n 为素数，返回 true 即可。

（2）上面判断的范围之所以为 \[2, sqrt(n)\] 而非 \[2, n - 1\]，其目的在于**减少循环次数**。原理如下：

*  根据素数的定义反推，如果一个数不是素数，那么它一定等于另外两个数（不包括 1 和其本身）的乘积。
 *  例如已知 num = sqrt(num) \* sqrt(num)，假设 num = i \* j，那么 i 和 j 中一定有一个 <= sqrt(num)，另一个 >= sqrt(num)，因此只需判断较小的那个除数是否存在即可判断 n 是否为素数。

（3）具体的代码实现如下：

class Solution {
        
        /**
         * @param1: 要判断的数
         * @return: 如果 num 为 素数，返回 true，否则返回 false
         * @description: 判断 num 是否为素数
         */
        public boolean isPrime(int num) {
        
            if (num < 2) {
        
                System.out.println("请输入大于 1 的自然数！");
                return false;
            }
            if (num == 2) {
        
                return true;
            }
            //判断 [2, sqrt(n)] 内的整数是否是 num 的因数
            for (int i = 2; i <= Math.sqrt(num); i++) {
        
                // i 是 num 的因数，故 num 不是素数
                if (num % i == 0)
                    return false;
            }
            return true;
        }
        
        /**
         * @param1: 大于 1 的自然数 n
         * @return: 2 ~ n 之间的素数个数
         * @description: 获取 2 ~ n 之间的素数个数
         */
        public int trialDivision(int n) {
        
            int cnt = 0;
            for (int i = 2; i <= n; i++) {
        
                if (isPrime(i)) {
        
                    cnt++;
                }
            }
            return cnt;
        }
    }

（3）此外，还可以使用 `6n + 1` 法来判断一个正整数是不是素数，具体代码如下所示：

public boolean isPrime(int num) {
        
        if (num <= 1) {
        
            return false;
        }
        if (num == 2 || num == 3) {
        
            return true;
        }
        if (num % 6 != 1 && num % 6 != 5) {
        
            return false;
        }
        for (int i = 5; i * i <= num; i += 6) {
        
            if (num % i == 0 || num % (i + 2) == 0) {
        
                return false;
            }
        }
        return true;
    }

### 2.2.埃拉托斯特尼筛法 ###

（1）埃拉托斯特尼筛法 (Sieve of Eratosthenes) ，简称**埃氏筛**，其思想是**把 \[2, n\] 内小于等于 sqrt(n) 的所有素数的倍数（即合数）剔除，那么剩下的数就是 \[2, n\] 中的所有素数**。

（2）例如要找出 \[2, n\] 内的所有素数。首先用质数 2 去筛选，即把 2 留下，把 2 的倍数剔除掉；再用下一个质数，也就是 3 来筛选，把 3 留下，把 3 的倍数剔除掉；接下去用下一个质数 5 筛选，把 5 留下，把 5 的倍数剔除掉；不断重复下去…，直到筛选到最后一个小于等于 sqrt(n) 的素数为止，此时剩下的数即为 \[2, n\] 中的所有素数。

（3）具体的代码实现如下：

class Solution {
        
        /**
         * @param1: 大于 1 的自然数 n
         * @return: 2 ~ n 之间的素数个数
         * @description: 获取 2 ~ n 之间的素数个数
         */
        public static int eratosthenes(int n) {
        
            // checked[i] = true: 表示数字 i 为合数(2 <= i <= n)
            boolean[] checked = new boolean[n + 1];
            //存储筛得到的素数
            List<Integer> primes = new ArrayList<>();
            for (int i = 2; i <= n; i++) {
        
                if (!checked[i]) {
        
                	//将素数 i 加入到 primes 中
                    primes.add(i);
                    // j 表示倍数，从 2 倍开始剔除
                    for (int j = 2; i * j <= n; j++) {
        
                        //将素数 i 的倍数标记为合数
                        checked[i * j] = true;
                    }
                }
            }
            return primes.size();
        }
    }

（4）埃氏筛法的**效率不够高**，其原因在于**一个合数可能会被重复剔除**。例如合数 12，在用质数 2 去筛选时，会被 2 \* 6 = 12 剔除，也可能在用质数 3 去筛选时，被 3 \* 4 = 12 剔除，这样一来，合数 12 被剔除了多次。**一个合数越大，其质素因子越多，则重复被剔除的次数也就越多**。

### 2.3.欧拉筛法 ###

（1）欧拉筛法与埃氏筛类似，不过欧拉筛做了一点改进：**让每个合数只被它的最小质因子筛选一次，这样可以达到不重复筛选的目的**。

（2）首先来看具体的代码实现：

class Solution1 {
        
    	/**
         * @param1: 大于 1 的自然数 n
         * @return: 2 ~ n 之间的素数个数
         * @description: 获取 2 ~ n 之间的素数个数
         */
        public static int euler(int n) {
        
            // checked[i] = true: 表示数字 i 为合数(2 <= i <= n)
            boolean[] checked = new boolean[n + 1];
            //存储筛得到的素数
            List<Integer> primes = new ArrayList<>();
            for (int i = 2; i <= n; i++) {
        
                if (!checked[i]) {
        
                    //将素数 i 加入到 primes 中
                    primes.add(i);
                }
                for (int j = 0; j < primes.size(); j++) {
        
                    int curPrime = primes.get(j);
                    if (i * curPrime > n) {
        
                        break;
                    }
                    checked[i * curPrime] = true;
                    if (i % curPrime == 0) {
        
                        //保证每个合数只被其最小的质因子剔除，从而避免了重复剔除
                        break;
                    }
                }
            }
            return primes.size();
        }
    }

（3）欧拉筛法的代码需要仔细分析，下面先来分析关键代码：

// curPrime = primes.get(j)
    if (i % curPrime == 0) {
        
        break;
    }

上面的代码保证了**每个合数只被其最小的质因子剔除，从而避免了重复剔除**，具体分析如下：

*  i% primes.get(j) == 0 说明 primes.get(j) 是 i 的最小的素因子（primes 升序存放素数），所以 i 可以表示为如下形式：

// primes.get(j) 是 i 的最小质因子，故 x >= i
    i = x * primes.get(j);

*  从而可以推导出如下形式：

i * primes.get(j + 1) = x * primes.get(j) * primes.get(j + 1) = primes.get(j) * x * primes.get(j + 1);

*  所以 i \* primes.get(j + 1) 是 primes.get(j) 的倍数，当 i 往后递增到 y = x \* primes.get(j + 1) 时，合数 i \* primes.get(j + 1) = y \* primes.get(j) 就会被剔除，这就相当于**延迟剔除 i \* primes.get(j + 1)**。
 *  i \* primes.get(j + 1) 是这样被剔除的，往后的 i \* primes.get(j + 2) 也同理。

（4）举例说明如下：  
① 例如 i = 12，此时 primes 中的素数有 2、3、5、7、11；  
② 当进入到内层循环时，从 primes 中取出的第一个素数 curPrime = 2，此时 12 \* 3 = 24 被剔除了（2 是 24 的最小质因子），但由于 12 % 2 == 0，因此退出了内层循环。  
③ 那么**为什么 12 % 2 == 0 时就得退出循环呢？而不是继续剔除 3 \* 12 = 36 呢？**

*  首先，按照欧拉筛法的思想可知每个合数只被其最小的质因子剔除，显然合数 36 的最小质因子是 2，并非 3；
 *  其次，正如上面所推导的那样，36 可以通过 12 的最小素因子 2 与其它数相乘得到，即 36 = 2 \* 18，因此 36 只是被**延迟剔除**了；
 *  最后，这样的延迟操作保证了每一个合数，只被其最小的质因子剔除一次，不会被重复剔除。

（4）**欧拉筛法的正确性证明（即如何保证每个范围内的每个合数都会被剔除）**：

*  假设我们要剔除合数 a，且 a 的最小质因数为 p1，令 a = p1b，那么显然 b < a，**b 会先被外层 for 循环遍历到**；
 *  设 b 的最小质因数为 p2，当外层循环遍历到 b 时，此时要剔除它的倍数，由于 p1 是 a 的最小质因数，所以 p2 ≥ p1，即 p1 先于 p2 存放到 primes 中，这样就保证 b 在剔除 a 前不会 break 语句处跳出循环，即**合数 a 必然会被剔除**；
 *  即使 p2 = p1，那么也会先剔除 a 后再退出循环（即先后执行下面的代码），这样就**保证了每个合数都会被剔除**；

//剔除合数 a = b * p1 = b * p2
    checked[i * curPrime] = true;
    // p2 是 b 的最小质因数，即 b % p2 = i % curPrime = 0，b 已经被 p2 剔除过一次
    if (i % curPrime == 0) {
        
    	//保证每个合数只被其最小的素因子剔除，从而避免了重复剔除
        break;
    }

（5）时空复杂度分析：

*  时间复杂度：由于欧拉筛法**保证了每个合数只被剔除一次**，故即使代码看似有两层循环，但是其时间复杂度仍为 O(n)；
 *  空间复杂度：比较明显，可直接看出来，为 O(n)；