How To Solve: Prime Numbers
Attached pdf of this Article as SPOILER at the top! Happy learning! Hi All,
I have posted a video on YouTube to discuss about
Prime NumbersAttached 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 numberOnly positive numbers can be prime numbersGeneric Form of Prime NumbersAll Prime Numbers (apart from 2 and 3) can be written as
¤ 6n + 1 or
¤ 6n - 1Example
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
Attachment:
img-1.JPG [ 66.19 KiB | Viewed 1024 times ]
Sample ProblemsQ1. Check if a 123 is prime number or notSolution:
Attachment:
img-2.JPG [ 64.58 KiB | Viewed 982 times ]
¤ 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 notSolution:
Attachment:
img-3.JPG [ 62.36 KiB | Viewed 1023 times ]
¤ 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!