CodeArena

如何高效寻找素数

::: tip 素数

如果一个数只能被1和它本身整除，那么这个数就是素数。

:::

实现一个函数，输入一个正整数n，函数返回区间[2,n)中素数的个数。

函数签名如下：int countPrimes(int n)

一般实现

1
/***
2
 * @Description: [2, n)素数的个数
3
 * @Author: Mr.Tong
4
 */
5
int countPrimes(int n) {
6
    int count = 0;
7
    for (int i = 2; i < n; i++) {
8
        if (isPrime(i)) {
9
            count++;
10
        }
11
    }
12
    return count;
13
}
14

15
/***
11 collapsed lines
16
 * @Description: 判断一个数是不是素数
17
 * @Author: Mr.Tong
18
 */
19
boolean isPrime(int n) {
20
    for (int i = 2; i < n; i++) {
21
        if (n % i == 0) {
22
            return false;
23
        }
24
    }
25
    return true;
26
}

分析问题：该算法的时间复杂度为O(n^2)，使用isPrime函数一个一个的进行判断不是高效的做法，而且就算是使用isPrime函数，也是存在计算冗余的。

稍加优化

isPrime函数是可以进行优化的，优化代码如下：

1
/***
2
 * @Description: 判断一个数是不是素数
3
 * @Author: Mr.Tong
4
 */
5
boolean isPrime(int n) {
6
    for (int i = 2; i * i <= n; i++) {
7
        if (n % i == 0) {
8
            return false;
9
        }
10
    }
11
    return true;
12
}

i不需要遍历到n，只需要遍历到sqrt(n)即可，这是因为sqrt(n)是反转临界点，一个数等于两个数相乘，中间的临界点就是sqrt(n)*sqrt(n)，[2,sqrt(n)]之间如果找不到可整除的因子，那么[sqrt(n),n]之间也肯定找不到可整除的因子了，因为是后半部分是前半部分的因子交换所得，这就叫做“乘法因子的交换性”。

高效实现

使用“筛数法”进行实现，2是素数，那么在n的范围中，2的倍数就不再是素数了；3是素数，那么在n的范围中，3的倍数就不再是素数了。

1
/***
2
 * @Description: 筛数法实现求解素数个数
3
 * @Author: Mr.Tong
4
 */
5
int countPrimes(int n) {
6
    //各个数的标记
7
    boolean[] isPrime = new boolean[n];
8
    //填充都为true
9
    Arrays.fill(isPrime, true);
10
    //从头开始，把所有n范围内的素数的倍数都标记为false
11
    for (int i = 2; i < n; i++) {
12
        //如果i为素数
13
        if (isPrime[i]) {
14
            //实际标记过程
15
            for (int j = 2 * i; j < n; j += i) {
12 collapsed lines
16
                isPrime[j] = false;
17
            }
18
        }
19
    }
20
    //求解true的个数
21
    int count = 0;
22
    for (int i = 0; i < isPrime.length; i++) {
23
        if (isPrime[i]) count++;
24
    }
25
    //最后结果去掉两个，因为0和1也都是true
26
    return count - 2;
27
}

上述的过程仍然是可以进行优化的，优化的地方主要有两点：

外层循环：因为乘法因子的对称性，遍历范围可以设置为[2,sqrt(n)]。
内层循环：j每次都从2开始存在冗余计算，只需要从i的平方开始标记即可。

重新优化后的代码：

1
/***
2
 * @Description: 筛数法实现求解素数个数
3
 * @Author: Mr.Tong
4
 */
5
int countPrimes(int n) {
6
    //各个数的标记
7
    boolean[] isPrime = new boolean[n];
8
    //填充都为true
9
    Arrays.fill(isPrime, true);
10
    //从头开始，把所有n范围内的素数的倍数都标记为false
11
    for (int i = 2; i * i <= n; i++) {
12
        //如果i为素数
13
        if (isPrime[i]) {
14
            //实际标记过程
15
            for (int j = i * i; j < n; j += i) {
12 collapsed lines
16
                isPrime[j] = false;
17
            }
18
        }
19
    }
20
    //求解true的个数
21
    int count = 0;
22
    for (int i = 0; i < isPrime.length; i++) {
23
        if (isPrime[i]) count++;
24
    }
25
    //最后结果去掉两个，因为0和1也都是true
26
    return count - 2;
27
}

这样的算法有一个名字，叫做Sieve of Eratosthenes，该算法的时间复杂度为O(NloglogN)。

高频面试

如何高效寻找素数

一般实现

稍加优化

高效实现