Page 141 - Ganit Kaushal

To Find All Primes from 1 to 100: (Sieve of Eratosthenes)

Eratosthenes was an ancient Greek mathematician, poet, and astronomer. He was born
in 276 BC in Cyrene, now part of modern-day Libya. Eratosthenes proposed a simple
algorithm for finding prime numbers. This algorithm is known in mathematics as the Sieve
of Eratosthenes.
The ‘Sieve of Eratosthenes’ is an interesting ancient algorithm for finding all prime numbers Eratosthenes
up to any given limit. (276BC–194BC)
Here we will use it only up to 100. So, take a square grid paper and write the numbers 1–100 on it.

Now, just follow the steps given below and see what 1 2 3 4 5 6 7 8 9 10
happens. 11 12 13 14 15 16 17 18 19 20

Step 1: Cross out 1 because it is neither prime nor composite. 21 22 23 24 25 26 27 28 29 30
Step 2: Circle 2, and then cross out all multiples of 2 after 31 32 33 34 35 36 37 38 39 40
that, i.e., 4, 6, 8, and so on. 41 42 43 44 45 46 47 48 49 50
Step 3: You will find that the next uncrossed number is 3. 51 52 53 54 55 56 57 58 59 60
Circle 3 and then cross out all the multiples of 3 after that, 61 62 63 64 65 66 67 68 69 70
i.e., 6, 9, 12, and so on.
71 72 73 74 75 76 77 78 79 80
Step 4: The next uncrossed number is 5. Circle 5 and then
cross out all the multiples of 5 after that, i.e., 10, 15, 20, 81 82 83 84 85 86 87 88 89 90
and so on. 91 92 93 94 95 96 97 98 99 100

Step 5: Continue this process till all the numbers in the list are either circled or crossed out.
All the circled numbers are prime numbers and all the crossed-out numbers, other than 1, are composite numbers.
This method of finding prime numbers is called the ‘Sieve of Eratosthenes’.

The prime numbers from 1 to 100 are 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.

In total, there are 25 prime numbers between 1 and 100.

Types of Numbers

Even numbers: An even number is defined as a whole number that is a multiple of 2. Even numbers always
end with the digits: 0, 2, 4, 6 or 8. For example: 200, 112, 1008, 5116, 75374, etc.

Odd numbers: The numbers that are not multiples of 2 are called odd numbers. Odd numbers always end
with the digits: 1, 3, 5, 7 or 9. For example: 201, 113, 1005, 5117, 75379, etc.

Perfect numbers: If the sum of all the factors of a number (including the number itself) is equal to twice the
number, then the number is called a perfect number.
For example: Factors of 6 = 1, 2, 3, 6 and 1 + 2 + 3 + 6 = 12 = 2 × 6. Thus, 6 is a perfect number. Another
perfect number is 28 as 1 + 2 + 4 + 7 + 14 + 28 = 56 = 2 × 28.
Remember
Twin Primes
1. The HCF of two co-primes is 1.
The term twin primes is used for a pair of prime numbers that 2. The LCM of two co-primes is equal
to their product.
differ by two. 3. If a number ‘A’ is a factor of ‘B’, then
For example: (3, 5), (11, 13), (17, 19), (29, 31), (41, 43), the HCF (A, B) = A, and the LCM
(59, 61), (71, 73), (107, 109), etc. are twin prime pairs. (A, B) = B.

Prime Time 139