In this article, we will check whether an integer is a prime number or not in python.
What is Prime Number?
- If a whole number greater than 1, is divisible by the 1 and itself then it is known as Prime Number.
- A prime number is a number which is divisible by only two numbers: 1 and itself. So, if any number is divisible by any other number, it is not a prime number.
Different View of the Logic
- The number cannot divisible by any number between 2 to n-1.
- Test all divisors from 2 through n-1 (skip 1 and n)
Example-1:
def isPrime(n):
flag=False
if(n>1):
for i in range(2,n):
if n%i==0:
flag=True
break
return flag
#Driver program
num=int(input('enter number'))
res=isPrime(num)
if res!=True:
print(num , " is a prime number.");
else:
print(num , " is not a prime number.");
output:
enter number11
11 is a prime number.
Example-2: let's begin a better approach in this example so I want you to observe these examples
think about it let me tell you what is observation can you see that the maximum factor we are getting other than the number itself is n/2. it is never more than n/2. so, let's see for 17 we were going for 2 to 16 let me say factor of 15 is 1 3 5 15 factor of 16 1 2 4 8 16 can you see there is no factor between 8 and 16 that is from a by (n/2+1) and (n -1) there are no factors 9 10 11 12 So we are wasting our time in checking whether these numbers can divide 16 or not because because after n/2 if a number is to be divisible it has to be multiplied by the small numbers correct so, I get 51 the minimum number I need to multiply with to become hundred and it does not exist because if i multiply 51*2 to it will go beyond hundred and we already know that 2 X50 become hundred similarly from here 75 so, if we go beyond n/2 you will not find any factors so instead of running our loop from i from 2 to n what we can do we can simply run our loop from 2 to n/2 this will work. The number can’t divisible by any number between 2 to n/2.
def isPrime(n):
flag=False
i=2
while i<=n//2:
#condition for nonprime number
if n%i==0:
flag=True
break
i=i+1
return flag
#Driver program
num=int(input('enter number'))
res=isPrime(num)
if res!=True:
print(num , " is a prime number.");
else:
print(num , " is not a prime number.");
Example-3: The number can’t divisible by any number between 2 to sqrt(n) I think we can do better to improve your function use it take to reduce the number of divisors in the for loop. the trick to reduce the number of divisors in the for loop to see the trick let's look at all the factor of 36 as the product of two positive integer.
notice the factorization after the perfect square is the same as before it is just in reverse order.
In the range of products is the first factor is always increasing and the second factor is always decreasing 36 is a perfect square is equal to 6 x 6. In this way we can reduce the number of divisors, we can only check the divisor only from 2 to square root of n.
import math
def isPrime(n):
flag=False
i=2
while i<=math.sqrt(n):
#condition for nonprime number
if n%i==0:
flag=True
break
i=i+1
return flag
#Driver program
num=int(input('enter number'))
res=isPrime(num)
if res!=True:
print(num , " is a prime number.");
else:
print(num , " is not a prime number.");
Example-4: A number which having only two factors is known as prime number for e.g.: - 3 having two factor 1 ,3 so 3 is a prime number 6 having more than two factor 1,2,3,6 so 6 is not a prime number.
def factorCount(n):
count=0
for i in range(1,n+1):
if n%i==0:
count+=1
return count
def isPrime(n):
c=factorCount(n)
if c==2:
return True;
else:
return False;
#Driver program
num=int(input('enter number'))
res=isPrime(num)
if res==True:
print(num , " is a prime number.");
else:
print(num , " is not a prime number.");
Read the more interesting article: click here