高频面试

如何高效寻找素数

素数

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

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

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

一般实现

/***
 * @Description: [2, n)素数的个数
 * @Author: Mr.Tong
 */
int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime(i)) {
            count++;
        }
    }
    return count;
}

/***
 * @Description: 判断一个数是不是素数
 * @Author: Mr.Tong
 */
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函数是可以进行优化的，优化代码如下：

/***
 * @Description: 判断一个数是不是素数
 * @Author: Mr.Tong
 */
boolean isPrime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

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

高效实现

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

/***
 * @Description: 筛数法实现求解素数个数
 * @Author: Mr.Tong
 */
int countPrimes(int n) {
    //各个数的标记
    boolean[] isPrime = new boolean[n];
    //填充都为true
    Arrays.fill(isPrime, true);
    //从头开始，把所有n范围内的素数的倍数都标记为false
    for (int i = 2; i < n; i++) {
        //如果i为素数
        if (isPrime[i]) {
            //实际标记过程
            for (int j = 2 * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    //求解true的个数
    int count = 0;
    for (int i = 0; i < isPrime.length; i++) {
        if (isPrime[i]) count++;
    }
    //最后结果去掉两个，因为0和1也都是true
    return count - 2;
}

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

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

重新优化后的代码：

/***
 * @Description: 筛数法实现求解素数个数
 * @Author: Mr.Tong
 */
int countPrimes(int n) {
    //各个数的标记
    boolean[] isPrime = new boolean[n];
    //填充都为true
    Arrays.fill(isPrime, true);
    //从头开始，把所有n范围内的素数的倍数都标记为false
    for (int i = 2; i * i <= n; i++) {
        //如果i为素数
        if (isPrime[i]) {
            //实际标记过程
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    //求解true的个数
    int count = 0;
    for (int i = 0; i < isPrime.length; i++) {
        if (isPrime[i]) count++;
    }
    //最后结果去掉两个，因为0和1也都是true
    return count - 2;
}

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