#204

Medium

LeetCode Problem Workspace

Count Primes

Count all prime numbers less than a given integer n using efficient array and math-based enumeration techniques.

Problem Statement

Given an integer n, return the total number of prime numbers that are strictly less than n. A prime number is defined as an integer greater than 1 with no divisors other than 1 and itself.

For example, if n = 10, the primes less than 10 are 2, 3, 5, and 7, resulting in an output of 4. Constraints include 0 <= n <= 5 * 10^6, and a brute-force check for each number is inefficient.

Examples

Example 1

Input: n = 10

Output: 4

There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2

Input: n = 0

Output: 0

Example details omitted.

Example 3

Input: n = 1

Output: 0

Example details omitted.

Constraints

0 <= n <= 5 * 106

Solution Approach

Sieve of Eratosthenes

Use a boolean array to mark numbers as prime or non-prime. Start from 2, and for each prime, mark all its multiples as non-prime. Count the remaining true values for the total primes.

Optimized Enumeration

Only check numbers up to the square root of n for marking multiples. This reduces unnecessary iterations and leverages the array plus math pattern for efficient prime elimination.

Early Exit and Edge Handling

Handle small values like n <= 2 separately to avoid array overhead. This ensures the solution covers all edge cases while maintaining speed for larger inputs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the sieve: marking multiples up to sqrt(n) yields O(n log log n), while space complexity is O(n) for the boolean array used to track primes.

What Interviewers Usually Probe

Checks if you understand the inefficiency of checking all numbers up to n individually.
Wants to see familiarity with array-based prime marking techniques.
Looks for mathematical reasoning to reduce redundant computation, especially using sqrt(n).

Common Pitfalls or Variants

Common pitfalls

Attempting to divide every number by all smaller numbers instead of using a sieve.
Not handling n <= 2 edge cases, which can lead to incorrect counts.
Incorrectly marking multiples or starting from 0 or 1 instead of 2.

Follow-up variants

Count primes in a range [m, n) instead of from 0 to n.
Return a list of prime numbers instead of the count, using the same sieve pattern.
Modify the sieve to support dynamic updates for multiple queries efficiently.

FAQ

What is the most efficient approach to solve Count Primes?

Using the Sieve of Eratosthenes with a boolean array is the fastest method, leveraging math to avoid redundant checks.

How do I handle n <= 1 in Count Primes?

Return 0 directly for n <= 1, since no prime numbers exist below 2, preventing unnecessary array operations.

Can I use trial division for this problem?

Trial division works but is inefficient for large n; the array plus math sieve pattern is recommended for optimal performance.

What is the time complexity of the optimized sieve?

The time complexity is O(n log log n), and space complexity is O(n) for the boolean array tracking prime numbers.

Does GhostInterview help with the array plus math pattern specifically?

Yes, it focuses on the Count Primes problem's array plus math pattern, guiding you through efficient marking and counting of primes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countPrimes(self, n: int) -> int:
        primes = [True] * n
        ans = 0
        for i in range(2, n):
            if primes[i]:
                ans += 1
                for j in range(i + i, n, i):
                    primes[j] = False
        return ans

Continue Practicing

#914 x of a kind in a deck of cards #952 largest component size by common factor #189 rotate array