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
Australia
UK
UAE
Singapore
Canada
New
Zealand
Malaysia
USA
India
South
Africa
Ireland
Saudi
Arab
Qatar
Kuwait
Hongkong
Copyright 2016-2023 www.programmingshark.com - All Rights Reserved.
Disclaimer : Any type of help and guidance service given by us is just for reference purpose. We never ask any of our clients to submit our solution guide as it is, anywhere.