Problem Statement (Simplified):
For a given number
Yesif it is prime, else print
Prime Numbers: Numbers that are divisible by 1 and itself only are known as Prime numbers.
Input: 2 13 14 Output: Yes No Explanation: Case-1: 13 is divisible by 1 and 13 only. So 13 is a prime number. Case-2: 14 is divisible by 1,2,7 and 14. So 14 is not a prime number.
Solving Approach :
1) We can check if there exists any number between
Ncompletely. If such a factor exists, that means the given number is not prime and we print
No. If no such number is found, we print
Yeswhich means the number is Prime.
2) But this approach takes
O(N)time complexity as we iterate every element from 1 to
N. We can go through the best online learning sites for programming and improve this time complexity more by using the more efficient approach.
1) We know if the number
Nis not Prime, it will have total factors more than 2. If we pick any two factors greater than , let’s say
b, then their product
a x bwill be always more than
2) So if we can’t find any factors less than or equal to the square root,
Nmust be prime.
3) So, We check numbers from 1 to , if a number is found which divides
Ncompletely, then the number is not prime. Else number is Prime.
Let’s assume, number to check is
500, its square root value is
22.360, so we check for all numbers from
500is not a
Lets take another number i.e.
42403, it’s square root is
205.919887335, so we check for all numbers from
205, we do not find any number in this range which divides