Count Primes

LeetCode 204 | Difficulty: Medium

Medium

Problem Description

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

Example 1:

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

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

- `0 <= n <= 5 * 10^6`

Topics: Array, Math, Enumeration, Number Theory

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 120 ms)

Metric	Value
Runtime	120 ms
Memory	N/A
Date	2018-04-12

Solution

public class Solution {
    public int CountPrimes(int n) {
if (n <= 2) return 0;
    bool[] sieves = new bool[n];//, true);
    for (int i = 2; i < sieves.Length; i++)
    {
        sieves[i]=true;
    }

    for (int i = 2; i * i <= n - 1; i++)
    {
        if (sieves[i])
        {
            for (int j = 2 * i; j <= n - 1; j += i)
            {
                if(sieves[j])
                    sieves[j] = false;
            }
        }
    }
    return sieves.Where(x=>x==true).Count();
    }
}

📜 2 more C# submission(s)

Submission (2018-04-12) — 120 ms, N/A

public class Solution {
    public int CountPrimes(int n) {
if (n <= 2) return 0;
    bool[] sieves = new bool[n];//, true);
    for (int i = 2; i < sieves.Length; i++)
    {
        sieves[i]=true;
    }

    for (int i = 2; i * i <= n - 1; i++)
    {
        if (sieves[i])
        {
            for (int j = 2 * i; j <= n - 1; j += i)
            {
                sieves[j] = false;
            }
        }
    }
    return sieves.Where(x=>x==true).Count();
    }
}

Submission (2018-04-12) — 176 ms, N/A

public class Solution {
    public int CountPrimes(int n) {
        if(n<=2) return 0;
        BitArray sieves = new BitArray(n,true);
    sieves[0]=false;
    sieves[1]=false;
    for (int i = 2; i*i <= n-1; i++)
    {
        if(sieves[i])
        {
            for (int j = 2*i; j <= n-1; j+=i)
            {
                sieves[j]= false;
            }
        }
    }
    int counter = 0;
    for (int i = 0; i < sieves.Length; i++)
    {
        if(sieves[i])
        {
            counter++;
        }
    }
    return counter;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Checking all the integers in the range [1, n - 1] is not efficient. Think about a better approach.

Hint 2: Since most of the numbers are not primes, we need a fast approach to exclude the non-prime integers.

Hint 3: Use Sieve of Eratosthenes.