我最近在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外)必小于等于其平方根。设k为最小约数 |
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
}
}
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) {
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 | 11 | 13 | 17 | 19 | 23 | 25 | 29 | 3->9,15,21,27 | ||||
i=5 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 5->25 |
版权声明
本博客所有的原创文章,作者皆保留版权。转载必须包含本声明,保持本文完整,并以超链接形式注明作者高爽和本文原始地址:http://ghsau.blogspot.my/2017/12/count-primes.html。
本博客所有的原创文章,作者皆保留版权。转载必须包含本声明,保持本文完整,并以超链接形式注明作者高爽和本文原始地址:http://ghsau.blogspot.my/2017/12/count-primes.html。
没有评论:
发表评论