Count the number of prime numbers less than a non-negative number, n.
Solution1：乘出非质数，再数质数
Time Complexity: O(n log log n) Space Complexity: O(N)
n/2 + n/3 + n/5 + … n/97 is not O(n), because the number of terms is not constant. [Edit after your edit: O(n2
) is too loose an upper bound.] A loose upper-bound is n(1+1/2+1/3+1/4+1/5+1/6+…1/n) (sum of reciprocals of all numbers up to n), which is O(n log n): see Harmonic number. A more proper upper-bound is n(1/2 + 1/3 + 1/5 + 1/7 + …), that is sum of reciprocals of primes up to n, which is O(n log log n). (See here or here.)
Solution2：Easyone, but Time Limit Exceeded
Time Complexity: O(Nsqrt(N)) Space Complexity: O(1)
Solution1 Code：
class Solution {
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
count++;
for (int j = 2; i * j < n; j++) {
notPrime[i * j] = true;
}
}
}
return count;
}
}
Solution2 Code：
class Solution2 {
public int countPrimes(int n) {
int count = 0;
for(int i = 1; i < n; i++) {
if (isPrime(i)) count++;
}
return count;
}
private boolean isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
}
