厄拉多塞筛素数筛选算法

2022年12月31日 · 197 字 · 1 分钟

厄拉多塞筛算法（Eratosthenes Sieve）是一种求素数的方法，由古希腊数学家厄拉多塞提出。它的原理是，给定一个数 n，从 2 开始依次将 $\sqrt n$ 以内的素数的倍数标记为合数，标记完成后，剩余未被标记的数为素数（从 2 开始）。如此可省去检查每个数的步骤，使筛选素数的过程更加简单。

算法

厄拉多塞筛算法具体步骤如下：

  1. 读取输入的数 n，将 2 到 n 的所有整数记录在表中
  2. 从 2 开始，划去表中所有 2 的倍数
  3. 由小到大寻找表中下一个未被划去的整数，再划去表中所有该整数的倍数
  4. 重复第（3）步，直到找到的整数大于$\sqrt n$为止
  5. 表中所有未被划去的整数均为素数

朴素的素数筛选算法如下：对给定的数字$i$，设定数字$j$从$2$遍历到$\sqrt i$，如果中间$i$能整除$j$，则$i$不是素数。该方法的时间复杂度为$O(n\sqrt n)$ ,$n$是数组长度，外层循环需要遍历$n$次，内层循环需要遍历$\sqrt n$次。

而厄拉多塞筛算法的时间复杂度为$O(n log(log(n)))$。

举例

这是一张来自维基百科的算法示意图。

算法示例

  1. 先从2开始遍历，将2的倍数(2,4,6,8,…)标记为为非素数
  2. 继续遍历，当前数字是素数时，继续将当前数字的倍数标记为非素数
  3. 直到所有数字标记完，重新标记数组，未被标记的就是素数

算法题

Leetcode 204. 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

代码实现

class Solution2 {

        // 厄拉多塞筛素数筛选算法
        // 1. 准备O(n)的数组，标识数字是否是质数，初始情况下全部是质数
        // 2. 从2开始遍历到sqrt(n),如果数字是质数，则i*i开始，后面i的倍数全是合数
        // 3. 从[2,n)筛选质数并统计
        public int countPrimes(int n) {
            if (n < 2) {
                return 0;
            }
            var isPrime = new boolean[n];
            Arrays.fill(isPrime, true);
            for (int i = 2; i * i < n; i++) { // 遍历一半即可
                if (isPrime[i]) { // 如果是质数，则将i平方开始的所有i的倍数设为合数
                    // 任意素数x的倍数有：2x, 3x, 4x, ..., x*x, (x+1)*x, ...
                    // 任意小于x*x的倍数都被之前的素数筛过滤过，如：2 过滤 2x, 4x, ...，3 过滤 3x, ...
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
            var count = 0;
            for (int i = 2; i < n; i++) {
                if (isPrime[i]) {
                    count++;
                }
            }
            return count;
        }
    }

时间复杂度: $O(nlog(log(n)))$。时间复杂度证明过程有点复杂，我暂时还没消化。

空间复杂度：$O(n)$。需要长度为$n$的数组标记是否素数。

qrcode