How do you approach Count Primes?

A brute force approach checks each number individually - can you do better?

What is the time complexity of Count Primes?

Time complexity: O(n log log n) - sieve complexity. Space complexity: O(n) - for the boolean array.

What are common mistakes on Count Primes?

Overflowing at an intermediate step even though the final answer fits. Assuming a modulo is non-negative. In most languages -1 % n is negative, which breaks cyclic indexing. Testing floating-point values for exact equality where integer arithmetic would have been exact.

Sitelet https://gitgood.dev/coding/count-primes

gitGood.dev

← Back to problems

Count Primes

EasyAlgorithms

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: 2, 3, 5, 7.

Example 2

Input: n = 0

Output: 0

Example 3

Input: n = 1

Output: 0

Constraints

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

Count Primes: approach, complexity and pitfalls

An easy math problem, graded against 8 test cases (5 of them hidden).

The pattern: Math

Number theory, digit manipulation, and closed-form reasoning.

Reach for it when you see: Primes, digits, base conversion, or a problem with a formula hiding behind it.

If you are stuck

Show the 3-step hint ladder

A brute force approach checks each number individually - can you do better?
Look up the Sieve of Eratosthenes algorithm.
Mark all multiples of each prime as composite, starting from 2.

The optimal approach

Show the approach: Sieve of Eratosthenes

Create a boolean array of size n, initially all true. Starting from 2, for each prime number, mark all its multiples as not prime. Count the remaining true values.

Optimization: start marking multiples from i*i (smaller multiples are already marked).

Time: O(n log log n) - sieve complexity
Space: O(n) - for the boolean array

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Math mistakes

These apply to the pattern as a whole, not just this problem.

Overflowing at an intermediate step even though the final answer fits.
Assuming a modulo is non-negative. In most languages `-1 % n` is negative, which breaks cyclic indexing.
Testing floating-point values for exact equality where integer arithmetic would have been exact.

← Back to problems

Count Primes

EasyAlgorithms

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: 2, 3, 5, 7.

Example 2

Input: n = 0

Output: 0

Example 3

Input: n = 1

Output: 0

Constraints

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

Count Primes: approach, complexity and pitfalls

An easy math problem, graded against 8 test cases (5 of them hidden).

The pattern: Math

Number theory, digit manipulation, and closed-form reasoning.

Reach for it when you see: Primes, digits, base conversion, or a problem with a formula hiding behind it.

If you are stuck

Show the 3-step hint ladder

A brute force approach checks each number individually - can you do better?
Look up the Sieve of Eratosthenes algorithm.
Mark all multiples of each prime as composite, starting from 2.

The optimal approach

Show the approach: Sieve of Eratosthenes

Create a boolean array of size n, initially all true. Starting from 2, for each prime number, mark all its multiples as not prime. Count the remaining true values.

Optimization: start marking multiples from i*i (smaller multiples are already marked).

Time: O(n log log n) - sieve complexity
Space: O(n) - for the boolean array

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Math mistakes

These apply to the pattern as a whole, not just this problem.

Overflowing at an intermediate step even though the final answer fits.
Assuming a modulo is non-negative. In most languages `-1 % n` is negative, which breaks cyclic indexing.
Testing floating-point values for exact equality where integer arithmetic would have been exact.