One of the best things that you can perform with python is checking the given number is prime or not. The prime numbers concept is very standard and remembered from the primary math class. If you want to learn what is a prime number and how to test the number is prime or not in python check out the following modules without any fail.
- What is a Prime Number?
- How to Test for Prime Numbers in Python?
- Python Program for prime number
- Python program to check whether a number is Prime or not
- Optimized Method
Explore more instances related to python concepts from Python Programs and get promoted from beginner to professional programmer level in Python Programming Language.
A prime number is any whole number (it must be greater than 1), whose only factors are 1 and itself, determining it can’t evenly be divided by any number (apart from 1 and itself, of course). Prime numbers include 2, 3, 5, 7, 11, 13, and so on until infinity.
The best way to resolve this issue is to repeat through all the numbers beginning from 2 to (N/2) with the help of a for loop and for every number check if it divides N. If we discover any number that divides, we return false. If we did not find any number between 2 and N/2 which divides N then it implies that N is prime and we will return True.
For grasping this concept, you need to get a good grip on the python programming concepts like Python if…else Statement, Python for Loop, and Python break and continue.
In Python, we can test for prime numbers quite efficiently using the following code:
if num > 1: for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") else: print(num,"is not a prime number")
First, the code monitors the number is greater than 1 (anything less than one can’t be a prime number because it isn’t whole). Then it checks to see if the number is divisible by any number between 2 and the number you’re checking. If it is divisible, then you’ll see from the output that the number is not prime. If it isn’t divisible by any of those numbers, then the message on the output will read “[num] is not a prime number.”
Let us perform the logic in python by using the defined function. Firstly, you can observe the algorithm for the prime number python program below:
- Initialize a for loop starting from 2 ending at the integer value of the floor of the square root of the number
- Check if the number is divisible by 2
- Repeat till the square root of the number is checked for.
- If the number is divisible by any of the numbers, the number is not prime
- Else, it is a prime number
import math def primeCheck(x): sta = 1 for i in range(2,int(math.sqrt(x))+1): # range[2,sqrt(num)] if(x%i==0): sta=0 print("Not Prime") break else: continue if(sta==1): print("Prime") return sta num = int(input("Enter the number: ")) ret = primeCheck(num)
Enter the number: 117 Not 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")
There are several ways to optimize the prime number program in Python:
- Rather than checking till n, we can check till √n because a larger factor of n needs to be a multiple of a smaller factor that has been already checked.
- The algorithm can be refined more by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = ?1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1.
def isPrime(n) : if (n <= 1) : return False if (n <= 3) : return True if (n % 2 == 0 or n % 3 == 0) : return False i = 5 while(i * i <= n) : if (n % i == 0 or n % (i + 2) == 0) : return False i = i + 6 return True if (isPrime(11)) : print(" true") else : print(" false") if(isPrime(15)) : print(" true") else : print(" false")