Python Program to Check Whether a Number is Prime or Not

In this article, we will check whether an integer is a prime no 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)
prime number in python
prime number in python
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
Prime Number in python
prime
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.
factor of 36
Factor of 36

notice the factorization after the perfect square is the same as before it 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

Read the more interesting article in python: click here

Leave a Reply

Your email address will not be published. Required fields are marked *