# Java Eratosthenes Sieve O(N lg lg N) solution with O(N) space

• Here is a solution that uses the Eratosthenes sieve for counting the primes: it's running time is O(N lg N) and it uses O(N) extra space.

``````public class CountPrimes {

public int countPrimes(int n) {

if(n <= 1) {
return 0;
}

final boolean[] primes = eratosthenesSieve(n);
int count = 0;
for(boolean prime : primes) {
if(!prime) {
count++;
}
}
return count;
}

private boolean[] eratosthenesSieve(int n) {

final boolean[] sieve = new boolean[n];
sieve[0] = true;
sieve[1] = true;

int sqrt = (int)Math.sqrt(n);
for(int num = 2; num <= sqrt; num++) {
if(!sieve[num]) {
for(int mul = num * num; mul < n; mul+=num) {
sieve[mul] = true;
}
}
}

return sieve;
}
}``````

• Here is the memory optimized version:

``````public class Solution {
public int countPrimes(int n) {
if(n <= 1) {
return 0;
}

final BitSet sieve = new BitSet(n);
sieve.set(0, true);
sieve.set(1, true);
int complex = 2;

int num = 2;
while(num * num < n) {
if(!sieve.get(num)) {

for(int mul = num * num; mul < n; mul += num) {
if(!sieve.get(mul)) {
sieve.set(mul, true);
complex++;
}
}
}

num++;
}

return n - complex;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.