Hi All,

I have posted a video on YouTube to discuss about Prime Numbers



Attached pdf of this Article as SPOILER at the top! Happy learning!

Following is Covered in the Video

Theory

¤ What is a Prime Number?
¤ Generic form of a Prime Number
¤ How to check if a number is prime?
¤ Sample Problems

What is a Prime Number?

Prime numbers are the numbers which have only two factors
¤ The number itself
¤ And 1

Example of Prime numbers are : 2, 3, 5, 7, 11, 13

2 is the only even prime number

Only positive numbers can be prime numbers


Generic Form of Prime Numbers

All Prime Numbers (apart from 2 and 3) can be written as
¤ 6n + 1 or
¤ 6n - 1

Example

7 = 6 +1 (of the form 6n+1)
11 = 12 – 1 (of the form 6n-1)
13 = 12 + 1 (of the form 6n+1)
17 = 18 -1 (of the form 6n-1)


How to check if a number (n) is prime?

¤ Divide the number by 6 and check if the remainder is 1 or 5
¤ If the remainder is not 1 or 5 then it is NOT a prime number
¤ If the remainder is 1 or 5 then it CAN be a prime number
¤ Divide the number by all prime numbers from 2 to Sqrt(n) and check if it is divisible by any of these numbers
¤ If the number is divisible by ANY of the prime numbers from 2 to Sqrt(n) then it is NOT a prime number
¤ If the number is NOT divisible by ALL the prime numbers from 2 to Sqrt(n) then it is a prime number




Sample Problems

Q1. Check if a 123 is prime number or not

Solution:



¤ 123 divided by 6 gives 3 as remainder which is NOT 1 or 5
¤ 123 is NOT a prime number

Q2. Check if a 127 is prime number or not

Solution:



¤ 127 divided by 6 gives 1 as remainder
¤ 127 CAN be a prime number
¤ We need to divide 127 by all prime numbers from 2 to Sqrt(127) and check if it is divisible by any of these numbers
¤ Closest integer to Sqrt(127) is Sqrt(121) = 11. So prime numbers from 2 to 11. 2,3,5,7,11
¤ 127 is NOT divisible by ALL the prime numbers 2,3,5,7,11.
¤ 127 is a prime number

Hope it Helps!