Prime numbers are fundamental building blocks in mathematics. They are natural numbers greater than 1 that have exactly two positive divisors: 1 and themselves. For example, 2, 3, 5, 7, and 11 are all prime numbers. The Sieve of Eratosthenes is an ancient and efficient algorithm for finding all prime numbers up to a specified limit.
The Sieve of Eratosthenes works by systematically eliminating composite numbers. We start by listing all numbers from 2 to our limit. Then we take the first prime, which is 2, and mark all its multiples as composite. Next, we find the next unmarked number, which is 3, and mark all its multiples. We continue this process until we've checked all primes up to the square root of our limit.
Let's work through a complete example finding all primes up to 30. We start by listing numbers 2 through 30. First, we mark all multiples of 2 as composite. Then we mark multiples of 3 that haven't been marked yet. Next, we mark multiples of 5. Since 7 squared equals 49, which is greater than 30, we can stop here. The remaining unmarked numbers are all prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.