Count Primes

Problem

Description:

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

Solution

Marking NotPrime Numbers: O(n lgn) time

public class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                count++;
                if (i > Math.sqrt(n)) continue;
                for (int j = 2; j * i < n; j++) notPrime[j*i] = true;
            }
        }
        return count;
    }
}

Analysis

The key idea in this solution is that: If a number is prime, then it's multiples are not primes
Therefore, we check from the first number 2
If we find a prime number, we increment count++
We avoid overflow by continuing the loop if i > Math.sqrt(n)
Then we mark multiples of current number as not prime in another for loop
We have notPrime so that we don't have to fill array after init

results matching ""

    No results matching ""