Sieve of Eratosthenes - Visualization

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given a number n, your task is to find all prime numbers less than or equal to n using the Sieve of Eratosthenes algorithm.

This classic algorithm eliminates the multiples of each prime number starting from 2, leading to an efficient list of primes up to n.

Examples❯

n Output Description
10 [2, 3, 5, 7] Standard case: All primes ≤ 10 using Sieve of Eratosthenes
1 [] Edge case: No primes ≤ 1, returns empty list
2 [2] Minimum prime number included: 2
20 [2, 3, 5, 7, 11, 13, 17, 19] Larger input: All primes up to 20
0 [] Zero input: No primes ≤ 0, returns empty list
"" [] Empty input treated as 0: returns empty list of primes
100 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] All prime numbers ≤ 100 using the sieve
3 [2, 3] Small odd number input: returns both 2 and 3
4 [2, 3] First composite number 4 excluded from primes
50 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] Moderate input size with correct primes filtered

Solution❯

Understanding the Problem

We are given a number n, and our goal is to find all prime numbers less than or equal to n. A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Instead of checking each number individually, we will use an efficient algorithm called the Sieve of Eratosthenes. This method uses the principle of marking the multiples of each prime starting from 2, so that only primes remain unmarked.

Step-by-Step Solution with Example

Let’s understand the Sieve of Eratosthenes with an example where n = 30.

Step 1: Create a list of size n+1 and assume all numbers from 2 to n are prime

We initialize a boolean array isPrime[] of size n + 1 with all entries set to true, except for index 0 and 1 which we mark as false because 0 and 1 are not prime numbers.

Step 2: Start from the first prime number, p = 2

We begin our iteration with the smallest prime number, which is 2.

Step 3: Mark all multiples of p (starting from p*p) as not prime

We mark all numbers like 4, 6, 8... up to 30 as false because they are multiples of 2.

Step 4: Move to the next number p = 3

Since isPrime[3] is still true, we know it’s prime. Now mark all multiples of 3 such as 9, 12, 15... up to 30 as false.

Step 5: Continue this process for the next numbers

We repeat this for the next numbers (4 is skipped since it’s already marked false). For p = 5, we mark 25 and 30 as false. We stop this loop when p * p > n (i.e., when p becomes greater than √n).

Step 6: Collect all numbers that are still marked true

Finally, we collect all indices in isPrime[] that are still true. These are our prime numbers up to n.

Final List for n = 30

The prime numbers ≤ 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Edge Cases

  • n = 0 or n = 1: There are no prime numbers. We return an empty list.
  • n = 2: The only prime number is 2.
  • Negative n: Prime numbers are not defined for negative integers. We return an empty list or raise an error depending on design.

Final Thoughts

The Sieve of Eratosthenes is one of the most efficient ways to find all primes up to a given number. It avoids redundant checks by eliminating multiples early. It is especially useful when n is large, and you need all primes up to that number quickly. Beginners should focus on understanding how marking from p*p helps reduce unnecessary operations.

Algorithm Steps❯

  1. Create a boolean array isPrime[] of size n+1 and initialize all entries as true. A value in isPrime[i] will finally be false if i is not a prime, else true.
  2. Start from the first prime number, p = 2.
  3. For each p, if isPrime[p] is true, mark all multiples of p as false (i.e., isPrime[i] = false for i = p*p to n, incrementing by p).
  4. Repeat the process for the next number until p*p <= n.
  5. All numbers i for which isPrime[i] is true are the prime numbers up to n.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void sieveOfEratosthenes(int n) {
    bool isPrime[n+1];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = false;
    isPrime[1] = false;

    for (int p = 2; p*p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p*p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    printf("Prime numbers up to %d: ", n);
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int n = 50;
    sieveOfEratosthenes(n);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n log log n)The Sieve of Eratosthenes runs in O(n log log n) time in all cases because it only marks multiples of primes starting from 2 up to sqrt(n). This is the most efficient known complexity for generating all primes up to n using this method.
Average CaseO(n log log n)Regardless of the input value of n, the average case involves marking off multiples of prime numbers, resulting in approximately O(n log log n) operations.
Worst CaseO(n log log n)The worst case still follows the same process of iterating through multiples of primes, up to sqrt(n), and marking them. This results in O(n log log n) time complexity even in the worst case.

Space Complexity❯

O(n)

Explanation: A boolean array of size n+1 is used to keep track of prime statuses for all numbers from 0 to n, which requires O(n) space.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...