PYTHON program to check if a number is prime or not

Python program to check if a number is prime or not

Naive Approach :

Key Idea: We can simply check for every number from 2 to n if it is a factor of n

Program :

Optimized Approach :

Key Idea: If n is not a perfect square then it can be represented as pairs of (a,b) i.e:(a*b)=n and for perfect square it will be a*a=n. So,a=sqrt(n).

This means that for a "n" if it is not a perfect square, we can say that the pairs occur in way where one pair is always less than sqrt(n) and other one greater than sqrt(n). :

Proof: Let's say I'm wrong ,then there can be 3 possibilities.

"If both a and b < sqrt(n)"

So,"a < sqrt(n) and b < sqrt(n) and a*b< n (which is wrong)".

"We can say the same for both a and b > sqrt(n)"

"Thus, the only way that's possible is if a < sqrt(n) and b > sqrt(n). "

"Except if the number is a perfect square in which case we need to check the sqrt(n) number as well. So overall, we can say we can just check from 2 to sqrt(n) , which can be very efficient for high values of n."

Program :

Output :