高频面试
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)
。