Count the number of prime numbers less than a non-negative number, n.
0 <= n <= 5 * 106
YouTube
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Input: n = 0
Output: 0
Input: n = 1
Output: 0
Last updated
Was this helpful?
Was this helpful?
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int countPrimes(int n) {
if(n <= 2) return 0;
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
int count = n-2;
for(int i = 2; i*i < n; i++) {
if(!isPrime[i]) continue;
for(int j = i; i*j < n; j++) {
if(isPrime[i*j]) {
isPrime[i*j] = false;
count--;
}
}
}
return count;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int countPrimes(int n) {
if(n <= 2) return 0;
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
int count = n/2;
for(int i = 3; i*i < n; i += 2) {
if(!isPrime[i]) continue;
for(int j = i*i; j < n; j += i*2) {
if(isPrime[j]) {
isPrime[j] = false;
count--;
}
}
}
return count;
}
}