204.Count Primes
question
Count the number of prime numbers less than a non-negative number, n.
Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Example 2:
Input: n = 0
Output: 0
Example 3:
Input: n = 1
Output: 0
题解:
最直观的当然是暴力解法,直接双重for循环,把每个小于n的质数都枚举出来。但如果不做优化,代码肯定运行超时。所以我们来考虑如何尽量减少for循环的迭代次数。
- 首先,>2的偶数m肯定有因子2和m/2,即>2的偶数肯定不是质数(减少筛选的次数)
- 其次,在判断一个整数m是否是质数,也需要用for循环去迭代。这时,我们考虑以m的算术平方根分界。假设m=a*b,如果当a<=sqrt(m),a只能取得1,相应的b也只能取m,此时m为质数。
- 最后,一些小细节——判断一个质数是否为质数,可以用isPrime进行标记;题目是<n,不是<=
代码
优化过后的暴力解法
class Solution {
public boolean isPrime(int x) {
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
public int countPrimes(int n) {
int numberCount = 0;
if (n < 3)
return 0;
numberCount++;
for (int i = 3; i < n; i += 2) {
if (isPrime(i))
numberCount++;
}
return numberCount;
}
}
另一种思路
假设现在输入的n值为10(利用空间换时间,ps:我们不需要去考虑arr[0]、arr[1]的值)
class Solution {
public int countPrimes(int n) {
//创建一个布尔类型的数组,如果索引值对应的值是true则为质数,反之不是质数
boolean[] arr = new boolean[n];
Arrays.fill(arr,true); //填充数据
int count = 0;
for( int i = 2; i*i<n;i++) {
if(arr[i]) {
//如果j为i的倍数,则j肯定不是质数
for(int j=i*2;j<n;j+=i){
arr[j] = false;
}
}
}
for(int i = 2;i<n;i++) {
if(arr[i]) {
count++;
}
}
return count;
}
};

Pay by WeChat