Count Primes - Practice Coding Problems

Count Primes - Problem

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

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Input & Output

Example 1 — Small Range

$ Input: n = 10

› Output: 4

💡 Note: Primes less than 10 are [2, 3, 5, 7], so count = 4

Example 2 — Very Small Range

$ Input: n = 2

› Output: 0

💡 Note: No primes less than 2, so count = 0

Example 3 — Edge Case

$ Input: n = 3

› Output: 1

💡 Note: Only prime less than 3 is [2], so count = 1

Constraints

0 ≤ n ≤ 5 × 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Given n = 10, find primes < 10

Process

Use sieve to identify primes: 2, 3, 5, 7

Output

Count = 4 primes found

Key Takeaway

🎯 Key Insight: Use sieve to mark composites instead of testing each number individually

Asked in

G Google 25 a Amazon 20 M Microsoft 15 f Facebook 12

The Sieve of Eratosthenes is the optimal approach. Key insight: instead of testing each number for primality, mark all multiples of each prime as composite. Best approach uses optimized sieve with Time: O(n log log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sieve of Eratosthenes	O(n log log n)	O(n)	Mark composites by crossing out multiples of each prime
Optimized Sieve	O(n log log n)	O(n)	Enhanced sieve with mathematical optimizations
Brute Force	O(n²)	O(1)	Check each number individually for primality

Sieve of Eratosthenes — Algorithm Steps

Create boolean array of size n, initially all true
Start with first prime (2), mark all its multiples as false
Find next unmarked number, mark its multiples
Count remaining true values

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

All numbers marked as potential primes

Mark 2's multiples

4, 6, 8 marked as composite

Mark 3's multiples

9 marked as composite (6 already marked)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int solution(int n) {
    if (n <= 2) return 0;
    
    // Create sieve array
    bool* sieve = (bool*)malloc(n * sizeof(bool));
    for (int i = 0; i < n; i++) {
        sieve[i] = true;
    }
    sieve[0] = sieve[1] = false;
    
    // Mark composites
    for (int i = 2; i * i < n; i++) {
        if (sieve[i]) {
            for (int j = i * i; j < n; j += i) {
                sieve[j] = false;
            }
        }
    }
    
    // Count primes
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (sieve[i]) count++;
    }
    
    free(sieve);
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log log n)

Sieve marks multiples of each prime, sum of work is n log log n

⚡ Linearithmic

Space Complexity

O(n)

Boolean array of size n to track prime status

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

5.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sieve of Eratosthenes — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler