五分钟小知识：如何用算法高效寻找素数？

古城微笑少年丶 2023-06-05 05:49 105阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | labuladong

来源 | labuladong

素数的定义很简单，如果一个数如果只能被 1 和它本身整除，那么这个数就是素数。

不要觉得素数的定义简单，恐怕没多少人真的能把素数相关的算法写得高效。本文就主要聊这样一个函数：

// 返回区间 [2, n) 中有几个素数 
    int countPrimes(int n)
    
    // 比如 countPrimes(10) 返回 4
    // 因为 2,3,5,7 是素数

你会如何写这个函数？当然可以这样写：

int countPrimes(int n) {
        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrim(i)) count++;
        return count;
    }
    
    // 判断整数 n 是否是素数
    boolean isPrime(int n) {
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                // 有其他整除因子
                return false;
        return true;
    }

这样写的话时间复杂度 O(n^2)，问题很大。**首先你用 isPrime 函数来辅助的思路就不够高效；而且就算你要用 isPrime 函数，这样实现也是存在计算冗余的**。

先来简单说下**如果你要判断一个数是不是素数，应该如何写算法**。只需稍微修改一下上面的 isPrime 代码中的 for 循环条件：

boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++)
            ...
    }

换句话说，`i`不需要遍历到`n`，而只需要到`sqrt(n)`即可。为什么呢，我们举个例子，假设`n = 12`。

12 = 2 × 6
    12 = 3 × 4
    12 = sqrt(12) × sqrt(12)
    12 = 4 × 3
    12 = 6 × 2

可以看到，后两个乘积就是前面两个反过来，反转的分界点就在`sqrt(n)`。

换句话说，如果在`[2,sqrt(n)]`这个区间之内没有发现可整除因子，就可以直接断定`n`是素数了，因为在区间`[sqrt(n),n]`也一定不会发现可整除因子。

这样，`isPrime`函数的时间复杂度降为了 O(sqrt(N))，**但是我们实现`countPrimes`函数其实并不需要这个函数**，以上只是希望读者明白`sqrt(n)`的含义，因为等会还会用到。

### 高效实现 countPrimes ###

高效解决这个问题的核心思路是和上面的常规思路反着来：

首先从 2 开始，我们知道 2 是一个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。

然后我们发现 3 也是素数，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素数了。

看到这里，你是否有点明白这个排除法的逻辑了呢？先看我们的第一版代码：

int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        // 将数组都初始化为 true
        Arrays.fill(isPrim, true);
    
        for (int i = 2; i < n; i++) 
            if (isPrim[i]) 
                // i 的倍数不可能是素数了
                for (int j = 2 * i; j < n; j += i) 
                        isPrim[j] = false;
    
        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrim[i]) count++;
    
        return count;
    }

![640?wx\_fmt=gif][640_wx_fmt_gif]图片来自 Wikimedia

如果上面这段代码你能够理解，那么你已经掌握了整体思路，但是还有两个细微的地方可以优化。

首先，回想刚才判断一个数是否是素数的`isPrime`函数，由于因子的对称性，其中的 for 循环只需要遍历`[2,sqrt(n)]`就够了。这里也是类似的，我们**外层**的 for 循环也只需要遍历到`sqrt(n)`：

for (int i = 2; i * i < n; i++) 
        if (isPrim[i]) 
            ...

除此之外，很难注意到**内层**的 for 循环也可以优化。我们之前的做法是：

for (int j = 2 * i; j < n; j += i) 
        isPrim[j] = false;

这样可以把`i`的整数倍都标记为`false`，但是仍然存在计算冗余。

比如`i = 4`时算法会标记 4 × 2 = 8，4 × 3 = 12 等等数字，但是 8 和 12 已经被`i = 2`和`i = 3`的 2 × 4 和 3 × 4 标记过了。

我们可以稍微优化一下，让`j`从`i`的平方开始遍历，而不是从`2 * i`开始：

for (int j = i * i; j < n; j += i) 
        isPrim[j] = false;

这样，素数计数的算法就高效实现了。其实这个算法有一个名字，叫做 Sieve of Eratosthenes。看下完整的最终代码：

int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for (int i = 2; i * i < n; i++) 
            if (isPrim[i]) 
                for (int j = i * i; j < n; j += i) 
                    isPrim[j] = false;
    
        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrim[i]) count++;
    
        return count;
    }

**该算法的时间复杂度比较难算**，显然时间跟这个嵌套 for 循环有关，其操作数应该是：

n/2 + n/3 + n/5 + n/7 + …

括号中是素数的倒数和。其最终结果是 O(N \* loglogN)，有兴趣的读者可以查一下该算法的时间复杂度证明。

以上就是素数算法相关的全部内容。怎么样，是不是看似简单的问题却有不少细节可以打磨呀？

![640?][640]

**有热门推荐?**

1.【程序员】

2.【GitHub】

3.【算法】

4.【数据结构】

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: /images/20230601/0c50df9176dc4ca8be836736f5fd636c.png
[640_wx_fmt_gif]: /images/20230601/6de621de104943f68c87749382836963.png
[640]: /images/20230601/820a38d78eff42dba2c614840abdcefd.png
[640_wx_fmt_jpeg 1]: /images/20230601/5fb4aecd157b46d1b93e8062b42dc0d0.png