Count Primes (Sieve of Eratosthenes)

📋

Problem

Imagine you are a cryptographer who needs to quickly find how many prime numbers exist below a certain threshold to generate secure keys.

Given an integer n, return the number of prime numbers strictly less than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

1 ≤ n ≤ 10^5

Edge cases: n = 0 → 0 (no primes less than 0)n = 1 → 0 (no primes less than 1)n = 2 → 0 (2 is prime but not less than 2)

</>

IDE

def countPrimes(n: int) -> int:public int countPrimes(int n)int countPrimes(int n)function countPrimes(n)

def countPrimes(n):
    # Write your solution here
    pass

class Solution {
    public int countPrimes(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countPrimes(int n) {
    // Write your solution here
    return 0;
}

function countPrimes(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: n (input) itself counted as primeCounting primes less than or equal to n instead of strictly less than n.✅ Change loop or count condition to consider primes strictly less than n, e.g. for i in range(2, n).

Wrong: Off-by-one errors causing undercount or overcountLoop boundaries incorrect, e.g. starting from 1 or ending at n instead of n-1.✅ Ensure loops start at 2 and end at n-1 for counting primes less than n.

Wrong: Incorrect marking of multiples leading to false primesMarking multiples starting from 2*p instead of p*p, causing redundant or missed markings.✅ Start marking multiples from p*p to avoid redundant work and ensure correctness.

Wrong: Timeout on large inputUsing brute force primality checks instead of sieve.✅ Implement Sieve of Eratosthenes with O(n log log n) complexity.

✓

Test Cases

Focus on handling small inputs and boundary conditions correctly.

Check your marking of multiples and loop boundaries carefully.

Optimize your solution to avoid timeouts on large inputs.

t1_01basic

Input{"n":10}

Expected4

⏱ Performance - must finish in 2000ms

The primes less than 10 are 2, 3, 5, and 7.

💡 Recall the definition of prime numbers and count those less than n.

💡 Use the Sieve of Eratosthenes to mark multiples as non-prime efficiently.

💡 Initialize a boolean array and count indices marked prime from 2 up to n-1.

Why it failed: Incorrect count for n=10 indicates failure to correctly mark primes or off-by-one error in range; fix by ensuring sieve marks multiples starting from 2 and counts primes strictly less than n.

✓ Correctly counts primes less than 10 using sieve logic.

t1_02basic

Input{"n":20}

Expected8

⏱ Performance - must finish in 2000ms

Primes less than 20 are 2, 3, 5, 7, 11, 13, 17, and 19.

💡 Extend the sieve to n=20 and count primes less than n.

💡 Remember to mark multiples of each prime starting from its square.

💡 Count all true entries in the sieve array from 2 to n-1.

Why it failed: Wrong count for n=20 usually means incorrect marking of multiples or counting n itself; fix by starting marking from p*p and counting only less than n.

✓ Correctly identifies all primes less than 20.

t2_01edge

Input{"n":0}

Expected0

⏱ Performance - must finish in 2000ms

No primes less than 0.

💡 Check how your code handles n less than 2.

💡 Primes start from 2, so counts for n < 2 should be zero.

💡 Return 0 immediately if n <= 2 to handle this edge case.

Why it failed: Failing this test means code does not handle n < 2 correctly; fix by returning 0 when n <= 2 before sieve.

✓ Correctly returns 0 for n=0.

t2_02edge

Input{"n":1}

Expected0

⏱ Performance - must finish in 2000ms

No primes less than 1.

💡 Remember primes start at 2, so n=1 has zero primes less than it.

💡 Check boundary conditions for small n values.

💡 Return 0 immediately if n <= 2 to handle this case.

Why it failed: Incorrect output for n=1 means boundary condition not handled; fix by returning 0 for n <= 2.

✓ Correctly returns 0 for n=1.

t2_03edge

Input{"n":2}

Expected0

⏱ Performance - must finish in 2000ms

2 is prime but not less than 2, so count is 0.

💡 Count primes strictly less than n, so exclude n itself.

💡 Ensure your loop or sieve counts only up to n-1.

💡 Return 0 if n <= 2 or count primes less than n excluding n.

Why it failed: Counting n itself as prime causes failure here; fix by counting primes strictly less than n.

✓ Correctly excludes n=2 and returns 0.

t3_01corner

Input{"n":3}

Expected1

⏱ Performance - must finish in 2000ms

Only prime less than 3 is 2.

💡 Check if your code correctly counts the smallest prime 2.

💡 Verify that your sieve initializes correctly and includes 2.

💡 Ensure counting starts from 2 and includes primes less than n.

Why it failed: Missing prime 2 in count means sieve initialization or loop start is wrong; fix by starting from 2 and including it if prime.

✓ Correctly counts prime 2 for n=3.

t3_02corner

Input{"n":4}

Expected2

⏱ Performance - must finish in 2000ms

Primes less than 4 are 2 and 3.

💡 Check if your sieve marks multiples correctly for small primes.

💡 Verify that multiples of 2 and 3 are marked non-prime properly.

💡 Count primes strictly less than n, including 2 and 3 here.

Why it failed: Incorrect count here often means marking multiples starting from 2 is wrong; fix by marking multiples starting from p*p.

✓ Correctly counts primes 2 and 3 for n=4.

t3_03corner

Input{"n":100}

Expected25

⏱ Performance - must finish in 2000ms

There are 25 primes less than 100.

💡 Beware of off-by-one errors in loops up to n.

💡 Check that you mark multiples starting from p*p, not from 2*p.

💡 Count primes strictly less than n, not including n if prime.

Why it failed: Off-by-one or incorrect marking of multiples causes wrong count; fix by looping i in [2, n-1] and marking multiples from p*p.

✓ Correctly counts 25 primes less than 100.

t4_01performance

Input{"n":100000}

Expectednull

⏱ Performance - must finish in 2000ms

Input n=100000 tests O(n log log n) sieve performance within 2 seconds.

💡 Use the Sieve of Eratosthenes for O(n log log n) time complexity.

💡 Avoid checking primality naively for each number.

💡 Mark multiples starting from p*p and stop at n to optimize.

Why it failed: TLE indicates brute force or inefficient primality checks; fix by implementing sieve with O(n log log n) complexity.

✓ Efficient sieve implementation passes performance test.

Practice

1. You are given a positive integer and repeatedly replace it by the sum of the squares of its digits. If this process eventually reaches 1, the number is considered "happy"; otherwise, it falls into a cycle that never reaches 1. Which approach guarantees detecting whether a number is happy in optimal time and space?

easy

A. Use a brute force approach storing all intermediate numbers in a hash set to detect cycles.

B. Use dynamic programming to store results for all numbers up to n to avoid recomputation.

C. Use a greedy approach that always picks the largest digit to speed up convergence.

D. Use Floyd's Cycle Detection algorithm (Tortoise and Hare) to detect cycles without extra space.

Solution

1. Step 1: Understand the problem pattern

   The problem involves detecting cycles in a sequence generated by repeatedly summing the squares of digits. Detecting cycles efficiently is key.

2. Step 2: Identify the optimal cycle detection method

   Floyd's Cycle Detection algorithm uses two pointers moving at different speeds to detect cycles in O(1) space, which is optimal compared to storing all seen numbers.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Floyd's algorithm detects cycles without extra memory [OK]

Hint: Cycle detection with two pointers uses constant space [OK]

Common Mistakes:

• Assuming greedy digit selection speeds up convergence
• Using DP unnecessarily increases space
• Brute force uses extra memory

2. You need to reverse the digits of a 32-bit signed integer, returning 0 if the reversed integer overflows. Which approach guarantees an optimal solution that handles overflow correctly without converting the integer to a string?

easy

A. Greedy approach that swaps digits from ends until the middle is reached

B. Dynamic programming to store reversed prefixes and build the result

C. Brute force string conversion and reversal without overflow checks

D. Recursive digit extraction with overflow checks before each digit append

Solution

1. Step 1: Understand problem constraints

   The problem requires reversing digits without string conversion and must handle overflow safely.

2. Step 2: Identify approach that meets constraints

   Recursive digit extraction with overflow checks ensures digits are reversed one by one and stops if overflow would occur, guaranteeing correctness and optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursive digit extraction handles overflow and sign correctly [OK]

Hint: Overflow-safe digit extraction is key [OK]

Common Mistakes:

• Using string reversal without overflow checks
• Greedy swaps fail on overflow
• DP is unnecessary overhead

3. You need to find the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently generates these numbers without checking every integer sequentially?

easy

A. Use a min-heap (priority queue) to always extract the smallest candidate and generate new multiples, avoiding duplicates.

B. Use a greedy algorithm that picks the smallest next multiple of 2, 3, or 5 from previously found numbers.

C. Use dynamic programming with a 2D table to store all factors and their counts for each number up to n.

D. Use brute force by checking each integer sequentially and verifying if its prime factors are only 2, 3, and 5.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, known as ugly numbers.

2. Step 2: Evaluate approaches for efficiency and correctness

   Brute force is too slow; min-heap approach is efficient but can be optimized further; dynamic programming with a 2D table is overcomplicated. The greedy approach with three pointers picks the smallest next multiple of 2, 3, or 5 from previously found numbers, efficiently generating the sequence without duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three-pointer greedy approach efficiently generates ugly numbers in ascending order without duplicates [OK]

Hint: Three-pointer greedy approach avoids duplicates and generates numbers in order [OK]

Common Mistakes:

• Assuming min-heap is the only efficient approach
• Thinking DP with 2D table is needed for prime factorization
• Believing brute force is efficient enough for large n

4. Examine the following buggy code snippet for Max Points on a Line:

from collections import defaultdict
import math

def maxPoints(points):
    n = len(points)
    if n <= 2:
        return n
    max_points = 1
    points.sort()
    for i in range(n):
        if max_points >= n - i or max_points > n // 2:
            break
        slopes = defaultdict(int)
        duplicates = 0
        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            if dx == 0 and dy == 0:
                duplicates += 1
                continue
            gcd = math.gcd(dy, dx)
            if gcd != 0:
                dy //= gcd
                dx //= gcd
            # Bug introduced here: missing normalization of slope sign
            slopes[(dy, dx)] += 1
        curr_max = max(slopes.values(), default=0) + duplicates + 1
        max_points = max(max_points, curr_max)
    return max_points

What is the bug in this code?

medium

A. Line missing slope sign normalization, causing (1,-1) and (-1,1) to be treated differently.

B. Duplicates are not counted, so points with same coordinates are ignored.

C. Vertical lines (dx=0) cause division by zero error.

D. Early termination condition breaks too early, missing maximum points.

Solution

1. Step 1: Identify missing slope sign normalization

   The code does not flip signs when dx < 0, so slopes like (1,-1) and (-1,1) are treated as different lines.

2. Step 2: Understand impact on grouping points

   This causes points on the same line but with opposite slope signs to be counted separately, undercounting max points.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sign normalization is critical to correctly group slopes [OK]

Hint: Check if slope sign normalization is done [OK]

Common Mistakes:

• Ignoring slope sign normalization
• Assuming gcd normalization is enough

5. Suppose you want to extend the happy number check to negative integers by applying the same digit square sum process on their absolute values. Which modification to the algorithm is necessary to correctly handle negative inputs?

hard

A. Add a check to convert negative input to positive before processing digits.

B. Modify digit extraction to handle negative digits directly without conversion.

C. Use recursion instead of iteration to handle negative inputs.

D. No modification needed; the existing algorithm works for negative numbers.

Solution

1. Step 1: Understand digit extraction for negatives

   Digit extraction using modulo and division assumes non-negative numbers; negative digits do not exist.

2. Step 2: Convert negative input to positive

   Taking absolute value ensures digit extraction works correctly and the sum of squares is computed properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Absolute value conversion fixes digit extraction for negatives [OK]

Hint: Digit extraction requires non-negative numbers [OK]

Common Mistakes:

• Trying to extract digits from negative directly
• Assuming recursion helps
• Ignoring sign issues