高频面试
About 4 min
如何高效寻找素数
素数
如果一个数只能被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)。