Sieve of Eratosthenes facts for kids
In mathematics, the Sieve of Eratosthenes is an old but clever way to find all prime numbers up to a certain limit. It's like a special filter that helps you sort out numbers.
This method works by finding and marking numbers that are not prime (these are called composite numbers). It starts with the first prime number, which is 2. Then, it marks all the numbers that are multiples of 2 (like 4, 6, 8, and so on). After that, it moves to the next unmarked number, which will be the next prime (3). It then marks all the multiples of 3 (like 6, 9, 12, etc.). This process continues until all the multiples of discovered primes have been marked. The numbers left unmarked are the prime numbers!
The idea for this "sieve" comes from Eratosthenes of Cyrene, a Greek mathematician who lived a very long time ago (in the 3rd century BCE). It's one of the best ways to find many smaller prime numbers quickly.
Contents
What is a Prime Number?
A prime number is a special kind of natural number. It can only be divided evenly by two numbers: the number 1 and itself. For example, 7 is a prime number because you can only divide it by 1 and 7. But 6 is not prime because you can divide it by 1, 2, 3, and 6.
How the Sieve Works: Step-by-Step
To find all the prime numbers up to a number, let's say n, using Eratosthenes' method, follow these steps:
- Step 1: Make a List. Write down all the numbers from 2 up to n. For example, if n is 30, your list would be: 2, 3, 4, ..., 30.
- Step 2: Start with the First Prime. The smallest prime number is 2. Let's call this number p.
- Step 3: Mark Multiples. Go through your list and mark all the multiples of p (which is 2). You start marking from 2 times p (which is 4). So, you mark 4, 6, 8, and so on, all the way up to n. Don't mark p itself!
- Step 4: Find the Next Prime. Look for the smallest number in your list that is greater than p and has not been marked yet. This new number is your next prime. Let this new number be p.
- Step 5: Repeat or Stop. If you found a new p, go back to Step 3 and repeat the process. If there are no more unmarked numbers greater than p, then you can stop.
- Step 6: Collect the Primes. When you stop, all the numbers that are not marked in your list are the prime numbers!
The cool thing about this method is that any number you pick as p will always be a prime number. If it wasn't prime, it would have already been marked by a smaller prime number before you got to it.
Making it Faster
There are a couple of ways to make the sieve even faster:
- Start Marking from p times p: Instead of starting to mark multiples from 2 times p, you can start from p times p (or p squared). Why? Because all the smaller multiples of p (like 2 times p, 3 times p, etc.) would have already been marked by smaller prime numbers. For example, when p is 5, you can start marking from 25 (5x5). Numbers like 10, 15, 20 would have already been marked by 2 or 3.
- Only Check Odd Numbers: You can start your list with only odd numbers (3, 5, 7, etc.) and skip 2. Then, when you mark multiples, you only mark odd multiples. This is because 2 is the only even prime number, and all other even numbers are multiples of 2.
Example: Finding Primes up to 30
Let's use the Sieve of Eratosthenes to find all prime numbers less than or equal to 30.
First, we list all the numbers from 2 to 30:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Step 1: Start with 2. We take 2, the first prime. Now, we cross out every 2nd number after 2 (all the multiples of 2):
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Step 2: Move to 3. The next unmarked number after 2 is 3. Now, we cross out every 3rd number after 3 (all the multiples of 3):
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Step 3: Move to 5. The next unmarked number after 3 is 5. Now, we cross out every 5th number after 5 (all the multiples of 5). Remember, we can start marking from 5x5=25:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Step 4: Move to 7. The next unmarked number after 5 is 7. We would cross out every 7th number after 7. However, we only need to check up to the square root of 30, which is about 5.4. Since 7x7 (49) is greater than 30, we don't need to mark any more numbers. All the multiples of 7 (like 14, 21, 28) are already crossed out because they are also multiples of smaller primes (like 2 or 3).
Final Primes: The numbers that are not crossed out are the prime numbers less than or equal to 30:
2 3 5 7 11 13 17 19 23 29
So, the prime numbers up to 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
See also
In Spanish: Criba de Eratóstenes para niños
