Session 3: Prime Numbers and Composite Numbers – Sieve of Eratosthenes, Definition, List, Facts and Examples

What is a Prime Number?

Let us try to arrange five balls in equal rows and columns. In how many ways can you arrange them?  

Five is arranged equally in a row. There are 5 ones.
OR
Five is arranged equally in a column. There is only one 5.

So, 1 and 5 are the factors of 5—also, [Math Processing Error]5÷1=5 and [Math Processing Error]5÷5=1.

Can you think of any other number which divides 5 exactly without leaving a remainder? No numbers, other than 1 and 5, divide 5 exactly.

Look at the following table:

Number	Factor
1	1
2	1, 2
3	1, 3
4	1, 2, 4
5	1, 5
6	1, 2, 3, 6
7	1, 7
8	1, 2, 4, 8
9	1, 3, 9
10	1, 2, 5, 10

Notice that 2, 3, 5, 7 have only two factors, 1 and the number itself. Other numbers have more than two factors. The numbers greater than 1 and only having two factors: 1 and the number itself are called prime numbers. 

What is a Composite Number?

Numbers with more than two factors are called composite numbers. Most numbers are composite numbers.

1) Which of the following numbers are prime?
i. 44
ii. 29
iii. 36
iv. 71

i. 44 has factors 1, 2, 4, 11, 22 and 44.
The number 44 has six factors, so it isn’t a prime number.
ii. 29 has a factors 1 and 29.
The number 29 has only two factors, so it is a prime number.
iii. 36 has factors 1, 2, 3, 4, 6, 9, 12, 18 and 36.
The number 36 has nine factors, so it isn’t prime.
iv. 71 has a factors 1 and 71.
The number 71 has only two factors, so it is a prime number.

Sieve of Eratosthenes

Eratosthenes, a Greek mathematician who lived in the third century B.C., found a technique to identify the prime numbers up to a given limit. In this technique, we select the smallest prime number from the list of numbers. For example, if we have a list of numbers from 2 to 100. We start with 2 and cross out all the multiples of 2, and these numbers will not be prime numbers since they are divisible by 2. Then, we proceed to the following number, which is not crossed out. Similarly, we cross every number, which is a multiple of the number. Finally, we have a number set with only prime numbers. This technique of identifying prime numbers is known as the Sieve of Eratosthenes.

Prime Numbers between 100 and 200: Rule to check

Examine whether the given number is divisible by any prime number less than 15, i.e. 2, 3, 5, 7, 11 and 13. If it is not divisible, it is a prime number; otherwise, it is a composite number.

There are 21 prime numbers between 100 and 200. They are 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

Prime Numbers between 100 and 400: Rule to check

Examine whether the given number is divisible by any prime number less than 20, i.e. 2, 3, 5, 7, 11, 13, 17 and 19. If it is not divisible, it is a prime number; otherwise, it is a composite number.

There are 53 prime numbers between 100 and 400. They are 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397

Is 1 a Prime Number?

According to the definition, prime numbers are numbers with two factors: 1 and the number itself. 1 has only one factor i.e. 1 itself. So, 1 is not a prime number.

Facts about Prime Numbers

Fact 1: 1 is neither prime nor composite.

Fact 2: 2 is the smallest prime number.

Fact 3: 2 is the only even prime number. All other even numbers are composite numbers.

Fact 4: Every prime except 2 is an odd number.

Fact 5: Composite numbers need not be even. 9 is the smallest odd composite number.

Fact 6: 90, 91, 92, 93, 94, 95, 96 are seven consecutive numbers less than 100, which are all composite having no prime number between them.

Fact 7: Every even number greater than 4 can be expressed as a sum of two odd primes, e.g., 16=11+5.

Fact 8: The number of primes is infinite. Here, infinite is used in the sense that no matter how many primes we have found, there are still more primes.

Fact 9: There is no largest prime number because otherwise, primes would be finite.

Fact 10: A natural number greater than 1 is either a prime or has a factor that is a prime.

DID YOU KNOW?

Magicicada, a group of insects that spend most of their lives as larvae underground. After precisely 13 or 17 years, they all emerge from their underground burrows and shed their skin to become adults. After a few days of flying around and breeding, they die. Why is it 13 or 17 years and not any other number? Scientists believe that Magicicadas evolved that way to avoid predators. If the bugs emerge, say, every 10 years, their life cycle might sync up with the life cycles of predators with 2-year life cycles and 5-year life cycles, since 2 and 5 are both factors of 10. But since 13 and 17 have no factors other than themselves and 1  – and very few predators have 13- or 17- year lifecycles – the cicadas have a much better shot at survival. Thanks to natural selection, the prime numbered life cycle became the norm!

What are Co-Primes or Relatively Prime Numbers?

Co-prime numbers is a set of numbers with just one common factor, i.e. 1, for example, (9 and 14), (4, 7, 9) are co-prime numbers. Co-prime numbers need not be prime numbers always. Two composite numbers like 9 and 14 also form a pair of co-primes.

Co-prime Numbers – Properties

Property 1: 1 is co-prime with every natural number existing in the number system.

Property 2: Any two prime numbers are always co-prime to each other, as they have only 1 as the common factor. For instance, 7 and 11 are two given prime numbers. Factors of 7 are 1, 7, and factors of 11 are 1, 11 respectively. The only common factor is 1, and consecutively they are co-prime.

Property 3: Two even numbers can never form a coprime pair as they always have 1 and 2 as the common factors.

Property 4: Any two consecutive numbers in the number system are always coprime to each other.

Property 5: The sum of any two coprime numbers is always coprime with their product. 5 and 7 are coprime numbers and have 12 as their sum and 35 as their product. Here, 12 is coprime with 35.
Some of the co-prime number pairs are (2, 3), (3, 4), (4, 15), (8, 9), (16, 25) etc.

Twin Prime Numbers

Twin prime numbers are prime numbers that differ by 2. Twin primes between 1 and 100 are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) and (71, 73). 5 is the only prime that belongs to two pairs.

Difference Between Twin Prime and Co-Prime Numbers

1. Twin numbers are always prime numbers, while co-prime numbers can be prime or composite.
2. All the pairs of twin prime numbers are co-prime, while the vice versa may not be true.
3. The difference between two twin primes is always 2, while the difference between two co-primes can be any number.

Abundant Numbers

In number theory, an abundant number is a positive integer, the sum of whose factors (including 1 but excluding the number itself) is greater than the number.
The factors of 12 other than 12 are 1, 2, 3, 4 and 6. If we add these numbers, the sum is more than 12. So, 12 is called an abundant number.

Deficient Number

In a deficient number, the sum of its factors is less than the number.
The factors of 10 other than 10 are 1, 2 and 5, and if we add these numbers, the sum is less than 10. Hence, 10 is a deficient number.

Perfect Number

A perfect number is a number that equals the sum of its factors. 
The factors of 6 other than 6 are 1, 2 and 3, and if we add these numbers, the sum equals 6. So, 6 is a perfect number. 6 is also the smallest perfect number. Other perfect numbers are 28, 496, and 8128.

---

Prime Numbers and Composite Numbers – Examples

Example 1

Prove that 91 is not a prime number.
First, list all the factors of 91.
91 at the very least has the factors 1 and 91. Keep looking for other factors.
Let’s divide 91 by 7.
91÷7=13
91 also has the factors 7 and 13.
Thus, 91 is not a prime number. It is a composite number.

Example 2

Is 1 a prime number or a composite number?
The number 1 has only one factor, so 1 is neither a prime number nor a composite number.

Example 3

Samay is working on a riddle.
“I am a number between 1 and 50. The sum of my digits is not prime, but I myself am prime. In a year, you will only see me 7 times. What number am I?”
How can Samay solve the riddle?First, look at the numbers between 1 and 50 that are prime. There are 15 prime numbers.

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47

Then, eliminate the numbers where the sum of the digits is prime.

Next, find the number you only see 7 times a year. Think about a calendar. 37 is not on a calendar at all. You see 11, 13, 17, 19 more than 7 times in a year. 

The answer to the riddle is 31. 

Example 4 

Which of the following is a prime number?

i. 151
ii. 183
iii. 269
iv. 319

i. The given number is 151.
To check whether it is prime or not, we check whether it is divisible by any primes 2, 3, 5, 7, 11 or 13.
We find that 151 is not divisible by any of the above numbers. So, it is a prime number.
ii. 183 has factors of 1, 3, 61 and 183. So it is not a prime number. 
iii. We find that 269 is not divisible by prime numbers 2, 3, 5, 7, 11, 13, 17 and 19. So, it is a prime number.
iv. The factors of 319 are 1, 11, 29 and 319. So, it is not a prime number.