Question

Write an algorithm to check the wheather input number is prime numbers or not?

Answer 1

Answer:

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Check whether n is a multiple of any integer between 2 and n.

#define ll long long  

#define M(x,i) memset(x,i,sizeof(x))  

 

for(i=2;i<n;++i) if (n%i==0) break;  

cout<<(i==n?"Prime Number":"Not a Prime");  

Time Complexity: O(n)

Every composite number has at least one prime factor less than or equal to square root of itself.

This property can be proved using counter statement. Let a and b be two factors of n such that a*b = n. If both are greater than sqrt(n), then a.b > sqrt(n), * sqrt(n), which contradicts the expression “a * b = n”.

Check whether n is multiple of any integer between 2 and sqrt(n).

Explanation: