How to Check Whether a Number is Prime or Not in Python?
What is a Prime Number?
In number theory, a number n is said to be if exactly two factors exist for that number 1 and the number itself. A number i is said to be a factor of number n if i divides n evenly.
List of some number and their factors:
n | Factors | Is Prime? |
1 | 1 | No |
2 | 1, 2 | Yes |
3 | 1, 3 | Yes |
4 | 1, 2, 4 | No |
7 | 1, 7 | Yes |
15 | 1, 3, 5, 15 | No |
From the table, we can see that 2, 3, and 7 are the prime numbers that have only two factors.
Important points:
- The smallest prime number is 2
- 1 is the factor of each number
- Every number is a factor of itself.
So, 1 and n are trivial factors of any number. Other than these two, there should not be any factor of a prime number. We can say that from 2 to n-1, we are unable to find a non-trivial factor that divides n without a remainder.
Algorithm to Check if a Number is Prime or Not in Python:
With the help of a loop in Python, form 2 to n-1 using the range () object in Python.
Code:
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
n = int(input("Enter a number: "))
result = is_prime(n)
if(result):
print(n," is prime number ")
else:
print(n," is not prime number")
Output:
Enter a number: 34
34 is not prime number
Enter a number: 45
45 is not prime number
Enter a number: 13
13 is prime number
Enter a number: 17
17 is prime number
In the code above, we travel through numbers from 2 to n-1 with the help of the range function by iterating i; if the number is divided by any of the digits between 2 to n-1, then we return false, and if the number is not divided by any of the numbers, then we return true, and we come out of the function. A number 'n' is taken as input form the user and checks the result by passing the number in function is_prime () and checks the result; if the result is true, we print the number as a prime number, and if the result is false, then we print the number 'n' is not a prime number. Since the function runs from 2 to n, the time complexity of the above function is O (n). We can optimize the above function.
Let's try to optimize the above function.
6 | 1, 2,-3, 6 |
10 | 1, 2,-5, 10 |
18 | 1, 2, 3, 6,-9, 18 |
From the above table, we can see that a number n that has only one factor is greater than n/2, which is n itself. So, we can se that we don need to run a loop from all the way up to n-1. We can run a loop from 2 to n/2 to check whether a number is prime or not.
The modified is_prime () function is,
Code:
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
n = int(input("Enter a number: "))
result = is_prime(n)
if(result):
print(n," is prime number ")
else:
print(n," is not prime number")
Output:
Enter a number: 34
34 is not prime number
Enter a number: 45
45 is not prime number
Enter a number: 13
13 is prime number
Enter a number: 17
17 is prime number
Enter a number: 2
2 is prime number
In the code above, we travel through numbers from 2 to n/2 with the help of the range function by iterating i; if the number is divided by any of the numbers between 2 to n/2, then we return false, and if the number is not divided by any of the numbers, then we return true, and we come out of the function. A number 'n' is taken as input form the user and checks the result by passing the number in function is_prime () and checks the result; if the result is true, we print the number as a prime number, and if the result is false, then we print the number 'n' is not a prime number. Since the function runs from 2 to n/2 th, the time complexity of the above function is O (n). We can optimize the above function.
Check whether the number is prime or not in the complexity of O (n1/2). We can check whether the given number is prime or not in the order of O (n1/2). Let's assume that n is a natural number and a is the factor n; then there exists a factor b for which an x b = n, or simply, ab = n. Consider an example of the number 18; the square root of 18 is approximately 4.24. And for the factors of 18 in pairs of (a, b), we can see that if a is less than 4.24, then b is greater than 4.24, and the factors are (2, 18) and (3,6).
The table given below gives the factors of 18 in pairs.
a | b |
1 | 18 |
2 | 9 |
3 | 6 |
For the number 36, the factors in the table below, since 36 is a perfect square, a = b = 6 is one of the factors.
a | b |
1 | 36 |
2 | 18 |
3 | 12 |
4 | 9 |
6 | 6 |
Code:
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
n = int(input("Enter a number: "))
result = is_prime(n)
if(result):
print(n,"is prime number")
else:
print(n,'is not prime number')
Output:
Enter a number: 13
13 is prime number
Enter a number: 34
34 is not prime number
Enter a number: 35
35 is not prime number
Enter a number: 5
5 is prime number
Enter a number: 17
17 is prime number
In the code above, we travel through numbers from 2 to -with the help of the range function by iterating i; if the number is divided by any of the numbers between 2 to , then we return false, and if the number is not divided by any of the numbers, then we return true, and we come out of the function. A number 'n' is taken as input form the user and checks the result by passing the number in function is_prime () and checks the result; if the result is true, we print the number as a prime number, and if the result is false, then we print the number 'n' is not a prime number. Since the function runs from 2 to , the time complexity of the above function is O (). We can optimize the above function.