Sifting Grains
- Author:
- Jaime Dianzon, Irina Boyadzhiev
- Topic:
- Division, Integers, Real Numbers
Why do we have to sift grains?
OBJECTIVE: To learn how to differentiate prime and composite numbers
In a previous lesson, we defined PRIME and COMPOSITE numbers.
Going Dutch: https://www.geogebra.org/m/xvdee7pg
In this lesson, you'll learn how to differentiate PRIME and COMPOSITE numbers. Since we defined COMPOSITE numbers as numbers that are NOT PRIME. We should be able to tell first which numbers are PRIME, and the rest will be COMPOSITE. Since numbers extend to infinity, we should expect an infinite number of PRIME numbers as well. We will not attempt to identify all of them, but it might be useful if we can at least identify PRIME numbers between 1 and 100.
The SIEVE OF ERATOSTHENES is customarily used for this purpose. Watch the video below to see how the system works.
Another way of identifying prime numbers between 1 and 100 without using the sieve is by applying divisibility rules.
In the previous lesson, we already identified the prime numbers between 1 and 20. So that leaves us with just the numbers between 21 and 100.
First, let's eliminate all EVEN numbers because aside from itself and 1, they can also be divided by 2. So, using the divisibility rule for 2, we can eliminate all numbers ending in 0, 2, 4, 6, or 8.
This implies that the remaining numbers to be tested are ODD and end in 1, 3, 5, 7, or 9. Now we know that those that end in 5 are NOT prime because aside from itself and 1, these numbers can be also divided by 5.
Now we only have to test numbers that end in 1, 3, 7, and 9.
Let's start with the numbers 21, 31, 41, 51, 61, 71, 81, and 91. ➽ 21, 51, and 81 can now be eliminated since they are divisible by 3. ➽ 91 can also be eliminated since it is divisible by 7.
Next, we test 23, 33, 43, 53, 63, 73, 83, and 93. ➽ 33, 63, and 93 can now be eliminated since they are also divisible by 3.
Now, we turn to 27, 37, 47, 57, 67, 77, 87, and 97. ➽ 27, 57, and 87 can now be eliminated since they are also divisible by 3. We can eliminate 77 since it is obviously divisible by 7.
Lastly, we look at 29, 39, 49, 59, 69, 79, 89, and 99. ➽ 39, 69, and 99 can now be eliminated since they are also divisible by 3.
In practice, we only have to use two divisibility rules to be able to identify all prime numbers from 1 to 100: divisibility by 3 (for most odd numbers) and by 7 (in the case of 77 and 91).
So let's list down all prime numbers between 1 and 100. There must be 25 of them: 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.
Without memorizing these prime numbers, go through the 20s, 30s, 40s, ..., 90s, and apply the divisibility rules for 3 and 7.
Here's an interactive applet that gives you practice on using the Sieve of Eratosthenes. Compare the results with the list above.
In this lesson, you learned how to differentiate prime and composite numbers.
In future lessons, you'll learn more about prime and composite numbers and their uses. Did you have FUN today?