求素数个数
我最近在leetcode上撸了一个小算法，虽然已经工作了五年，当看到每次代码提交后排名的提升，内心依然很有成就感。题目比较简单，求小于n的素数个数，素数也叫质数，具有以下特点：
- 正整数
- 只能被1和本身整除
- 1既不是素数也不是合数，所以最小的素数是2
根据上面的特点，我们还可以推断出：
- 除了2，其它的素数都是奇数
依据这一点，我们可以写出下面的实现：
class Solution {
public int countPrimes(int n) {
if (n < 3) {
return 0;
}
int count = 1;// 2
for (int i = 3; i < n; i += 2) {
// 只判断奇数是不是素数
boolean isPrime = true;
for (int j = 3; j * j <= i; j += 2) {
// 奇数不可能被偶数整除，所以只试除奇数
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
count++;
}
}
return count;
}
}j * j <= i相当于j <= Math.sqrt(i)，但速度会快一点，那为什么只需要判断到√i呢，因为对于一个非素数(合数)，其最小约数(除1外)必小于等于其平方根。
这个实现被Accept了，但时间复杂度较高，排名也很靠后。这个算法中，判断一个奇数i是不是素数，是通过试除小于等于√i的奇数来实现，这会有重复计算的场景，比如3和9，5和15，根据素数和合数的特点，可以推断出任意一个合数都可以分解成几个素数的乘机，所以我们可以通过试除小于等于√i的素数来判断i是不是素数，素数相对于奇数，无疑减少了很多判断次数。
class Solution {
public int countPrimes(int n) {
if (n < 3) {
return 0;
}
int count = 0;
int[] primes = new int[n / 2];
for (int i = 3; i < n; i += 2) {
// 只判断奇数是不是素数
boolean isPrime = true;
for (int j = 0; j < count && primes[j] * primes[j] <= i; j++) {
// 只试除素数
if (i % primes[j] == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primes[count++] = i;
}
}
return count + 1;// 2
}
}效果好了一些，但这个实现时间复杂度依然很高，比试除法更高效的是筛选法，筛选法的策略是将素数的倍数全部筛掉，剩下的就是素数了，下图很生动的体现了筛选的过程：
筛选的过程是先筛掉非素数，针对本文的题目，每筛掉一个，素数数量-1即可，上面说过素数的一个特点，除了2，其它的素数都是奇数，所以我们只需在奇数范围内筛选就可以了。
class Solution {
public int countPrimes(int n) {
if (n < 3) {
return 0;
}
int count = n / 2;// 筛掉一半偶数
boolean[] notPrime = new boolean[n];
for (int i = 3; i * i < n; i += 2) {// 只筛3≤i<√n奇数
if (!notPrime[i]) {
// 筛掉素数的奇数倍数
for (int j = i * i; j < n; j += 2 * i) {// 从i*i开始筛
if (!notPrime[j]) {
notPrime[j] = true;
count--;
}
}
}
}
return count;
}
}示例 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 备注 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
i=3 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 3->9,15,21,27 |
i=5 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 5->25 |
对于一个奇数i，会依次筛掉i*i,i(i+2),i(i+4),i(i+6)…i(i+2n)，那么为什么不筛3i,5i,7i…(i-4)i,(i-2)i呢，因为他们已经被筛过了，当我们要筛掉奇数i的倍数时，那么i之前的奇数(i-2,i-4…7,5,3)的倍数((i-2)i,(i-4)i…7i,5i,3i)已经被筛掉了，这个算法的效果还不错。
版权声明 本博客所有的原创文章，作者皆保留版权。转载必须包含本声明，保持本文完整，并以超链接形式注明作者高爽
我的博客在腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan
腾讯云开发者
