Count Primes

Count the number of prime numbers less than a non-negative number, n.

Solution: use sieve of Eratosthenes (wiki)

public class Solution {
    public int countPrimes(int n) {
        //Use sieve of Eratosthenes
        boolean notPrime[] = new boolean[n+2];
        //natural number 0 & 1 are not prime:
        notPrime[0] = notPrime[1] = true;
        for (int i = 2; i*i < n; i++) {
            if (!notPrime[i]) {
                int c = i*i;
                //mark the multiples of each prime as true
                while (c < n) {
                    notPrime[c] = true;
                    c += i;
                }
            }
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!notPrime[i]) count++;
        }
        return count;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s