Innings2
Create New Account

Sign in to Innings2

or

New Account     Reset Password     

Prime Time

    Common Multiples and Common Factors

    Jump Jackpot

    Figure it Out Exercises

    Prime Numbers

    Sieve of Eratosthenes

    Co-prime Numbers for Safekeeping Treasures

    Prime Factorization

    Divisibility Tests

    Fun with Numbers

    Summary

Powered by Innings 2

Reset Progress

This will delete your progress and chat data for all chapters in this course, and cannot be undone!

Glossary

Select one of the keywords on the left…

Prime Time > Sieve of Eratosthenes

Sieve of Eratosthenes

Can we list all the prime numbers from 1 to 100?

Here is an interesting way to find prime numbers. Just follow the steps given below and see what happens.

Step 1: Cross out 1 because it is neither prime nor composite.

Step 2: Circle 2, and then cross out all multiples of 2 after that, i.e., 4, 6, 8, and so on.

Step 3: You will find that the next uncrossed number is 3. Circle 3 and then cross out all the multiples of 3 after that, i.e., 6, 9, 12, and so on.

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, and so on.

Step 5: Continue this process till all the numbers in the list are either circled or crossed out.

All the circled numbers are numbers. All the crossed out numbers, other than , are numbers. This method is called the Sieve of Eratosthenes.

This procedure can be carried on for numbers greater than 100 also. Eratosthenes was a Greek mathematician who lived around 2200 years ago and developed this method of listing primes.

The Sieve of Eratosthenes

It turned out to be quite difficult to determine if a number is prime: you always had to find all its prime factors, which gets more and more challenging as the numbers get bigger. Instead, the Greek mathematician Eratosthenes of Cyrene came up with a simple algorithm to find all prime numbers up to 100: the Sieve of Eratosthenes.

1
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
First we need to write down all numbers up to 100.
We know that 1 is not prime, so we delete it.
The smallest prime number is 2. Any multiple of 2 can’t be prime, since it has 2 as a factor. Therefore we can cross out all multiples of 2.
The next number in our list is 3 – again a prime number. All multiples of 3 can’t be prime, since they have 3 as a factor. Therefore we can cross these out as well.
The next number, 4, is already crossed out so we move on to 5: it is a prime number and again we cross out all multiples of 5.
The next prime number must be , since 6 is crossed out. Once more, we cross out all of its multiples.
The next prime number is . Notice, however, that all of its multiples are . The same is actually true for all other remaining numbers. Therefore all these remaining numbers must be prime.

Now we can count that, in total, there are prime numbers less than 100.

1. We see that 2 is a prime and also an even number. Is there any other even prime?

Answer: . All other even numbers are divisible by , so they have more than two factors and are therefore .

2. Look at the list of primes till 100. What is the smallest difference between two successive primes? What is the largest difference?

Answer: The smallest difference is (between primes and ). The largest difference is (between primes 89 and 97).

3. Are there an equal number of primes occurring in every row in the table on the previous page? Which decades have the least number of primes? Which have the most number of primes?

Answer: , there are not equal numbers of primes in every row. The decades 9__0-99__ have the number of primes ( primes). The decades 1-10 and 11-20 have the most number of primes ( primes each).

Primes through the Ages

Prime numbers are the building blocks of all whole numbers. Starting from the time of the Greek civilisation (more than 2000 years ago) to this day, mathematicians are still struggling to uncover their secrets!

Food for thought: is there a largest prime number? Or does the list of prime numbers go on without an end? A mathematician named Euclid found the answer and so will you in a later class!

Fun fact: The largest prime number that anyone has 'written down' is so large that it would take around 6500 pages to write it! So they could only write it on a computer!

4. Which of the following numbers are prime: 23, 51, 37, 26?

Answer: 23 and 37 are . 51 is (divisible by 3 and 17). 26 is (divisible by 2 and ).

5. Write three pairs of prime numbers less than 20 whose sum is a multiple of 5.

Answer: (, ) sum = 5, (, ) sum = 15, (, ) sum = 20.

6. The numbers 13 and 31 are prime numbers. Both these numbers have same digits 1 and 3. Find such pairs of prime numbers up to 100.

Answer: (13, 31), (17, ), (37, ), (79, ).

7. Find seven consecutive composite numbers between 1 and 100.

Answer: 90, 91, 92, 93, , , are seven consecutive composite numbers.

8. Twin primes are pairs of primes having a difference of 2. For example, 3 and 5 are twin primes. So are 17 and 19. Find the other twin primes between 1 and 100.

Answer: (5, 7), (11, ), (29, ), (41, ), (59, ), (71, ).

9. Identify whether each statement is true or false. Explain. a. There is no prime number whose units digit is 4. b. A product of primes can also be prime. c. Prime numbers do not have any factors. d. All even numbers are composite numbers. e. 2 is a prime and so is the next number, 3. For every other prime, the next number is composite.

Answer:

a. - Numbers ending in 4 are even and greater than 2, so they are composite.

b. - A product of primes is always composite (except when it's a single prime).

c. - Prime numbers have exactly factors: and the number itself.

d. - The number is even and prime.

e. - After 3, all primes are odd, so the next number (even) is composite.

10. Which of the following numbers is the product of exactly three distinct prime numbers: 45, 60, 91, 105, 330?

Answer: 105 = 3 × × (three distinct prime factors).

11. How many three-digit prime numbers can you make using each of 2, 4 and 5 once?

Answer: three-digit prime numbers can be made. All arrangements (245, 254, 425, 452, 524, 542) are numbers and therefore .

12. Observe that 3 is a prime number, and 2 × 3 + 1 = 7 is also a prime. Are there other primes for which doubling and adding 1 gives another prime? Find at least five such examples.

Answer: 3 → ,

5 → ,

11 → ,

29 → ,

41 →