Count Primes

Problem

Given an integer n, return the number of prime numbers that are strictly less than n.

Examples

Example 1:

1
2
3
4
5

Input:
n = 10
Output:
 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

1
2
3
4

Input:
n = 0
Output:
 0

Example 3:

1
2
3
4

Input:
n = 1
Output:
 0

Solution

Method 1 - Naive

This solution exceeds time limit.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


public int countPrimes(int n) {
    n = n - 1;

    ArrayList<Integer> primes = new ArrayList<Integer>();

    if (n <= 1)
        return 0;
    if (n == 2)
        return 1;
    if (n == 3)
        return 2;

    primes.add(2);
    primes.add(3);

    for (int i = 4; i <= n; i++) {
        boolean isPrime = true;
        for (int p : primes) {
            int m = i % p;
            if (m == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            primes.add(i);
        }
    }

    return primes.size();
}

Method 2 - Using Sieve of Eratosthenes

This solution is the implementation of Sieve of Eratosthenes Algorithm. This is a well-known and efficient algorithm for finding all prime numbers up to a specified integer.

Sieve of Eratosthenes Algorithm

  1. Create a boolean array of size ( n ) and initialize all entries as true. Entries at index positions which are non-prime will be marked as false.
  2. Set the values for 0 and 1 as false (since 0 and 1 are not prime numbers).
  3. For each number ( p ) from 2 to ( \sqrt{n} ):
    • If ( p ) is still true in the array, it is a prime number.
    • Mark all multiples of ( p ) (starting from ( p \times p )) as false.
  4. Count the number of true values left in the array. These correspond to the prime numbers strictly less than ( n ).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class CountPrimes {
    public static int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        boolean[] isPrime = new boolean[n];
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }

        for (int p = 2; p * p < n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i < n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        int primeCount = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                primeCount++;
            }
        }

        return primeCount;
    }
}

Complexity

  • ⏰ Time complexity: O(n log(log(n)))
  • 🧺 Space complexity: O(n)