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


  • 0
    J

    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;
    }
    }

  • 0
    J

    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;
    }
    }

Log in to reply
 

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