目录

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

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 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 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 的最小质因数为 p₁，令 a = p₁b，那么显然 b < a，b 会先被外层 for 循环遍历到；
• 设 b 的最小质因数为 p₂，当外层循环遍历到 b 时，此时要剔除它的倍数，由于 p₁ 是 a 的最小质因数，所以 p₂ ≥ p₁，即 p₁ 先于 p₂ 存放到 primes 中，这样就保证 b 在剔除 a 前不会 break 语句处跳出循环，即合数 a 必然会被剔除；
• 即使 p₂ = p₁，那么也会先剔除 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)；