05 August 2008
Count the number of prime numbers less than a non-negative number, n.
Example:
1
2
3
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
这道题比较简单，给一个非负整数n，找到小于n的所以素数，不包括n自己。正常的做法就是从2循环到n-1，每个数都判断下是否是素数，判断是否是素数的办法如下：
1
2
3
4
5
6
7
8
9
10
11
//判断一个数是否是质数（素数）
public boolean isPrimeNumber(int num){
if(num == 2) return true;//2特殊处理
if(num < 2 || num % 2 == 0) return false;//识别小于2的数和偶数
for(int i=3; i<=Math.sqrt(num); i+=2){//从3开始，到平方根结束，每次+2，因为偶数肯定不是质数
if(num % i == 0){//识别被奇数整除
return false;
}
}
return true;
}
在Discuss区看到一个空间换时间的做法（https://leetcode.com/problems/count-primes/discuss/57588/My-simple-Java-solution），从2开始遍历，然后每次遇到质数的时候就开始计算后面的数字，标记true或者false，因为如果是合数则一定可以被前面的数乘以得到（证明略），接下来遇到即可直接判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int countPrimes(int n) {
if (n < 2) {
return 0;
}
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {//default值为false
count++;
for (int j = 2; i*j < n; j++) {//j从2开始
notPrime[i*j] = true;
}
}
}
return count;
}
}