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.
Comments
Loading comments...