Given a positive integer N, The task is to write a Python program to check if the number is prime or not.
Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are {2, 3, 5, 7, 11, ….}.
Examples :
Input: n = 11 Output: true Input: n = 15 Output: false Input: n = 1 Output: false
The idea to solve this problem is to iterate through all the numbers starting from 2 to (N/2) using a for loop and for every number check if it divides N. If we find any number that divides, we return false. If we did not find any number between 2 and N/2 which divides N then it means that N is prime and we will return True.
Below is the Python program to check if a number is prime:
# Python program to check if # given number is prime or not num = 11 # If given number is greater than 1 if num > 1: # Iterate from 2 to n / 2 for i in range(2, int(num/2)+1): # If num is divisible by any number between # 2 and n / 2, it is not prime if (num % i) == 0: print(num, "is not a prime number") break else: print(num, "is a prime number") else: print(num, "is not a prime number")
Output
11 is a prime number
Optimized Method
We can do the following optimizations:
Now lets see the code for the first optimization method ( i.e. checking till √n )
from math import sqrt # n is the number to be check whether it is prime or not n = 1 # no lets check from 2 to sqrt(n) # if we found any facto then we can print as not a prime number # this flag maintains status whether the n is prime or not prime_flag = 0 if(n > 1): for i in range(2, int(sqrt(n)) + 1): if (n % i == 0): prime_flag = 1 break if (prime_flag == 0): print("true") else: print("false") else: print("false")
Output
false