204-count-primes

Question

https://leetcode.com/problems/count-primes/description/

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

Example:

Thought Process

1. Typical Sqrt Root (TLE)
   1. One way we can test a number, n, is prime or not is simply try all the number between 2 and n - 1
   2. A little bit optimized way is test all the number up to sqrt root of n
   3. Time complexity for isPrime function, O(n^0.5) for all number up to n, is O(n^1.5)
   4. Space complexity O(1)
2. Sieve of Eratosthenes
   1. Every time we pick a number, we mark all its multiple as not prime. We can also use composite boolean array to save the initialization cost
   2. Time complexity O(n)
   3. Space complexity O(n)

Solution

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) count++;
        }
        return count;
    }

    private boolean isPrime(int num) {
        for (int f = 2; f * f <= num; f++) {
            if (num % f == 0) return false;
        }
        return true;
    }
}

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!prime[i]) continue;
            count++;
            for (int m = 2; m * i < n; m++) {
                prime[m * i] = false;
            }
        }
        return count;
    }
}

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] composite = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (composite[i]) continue;
            count++;
            for (int m = 2; m * i < n; m++) {
                composite[m * i] = true;
            }
        }
        return count;
    }
}

Additional