What is a Prime Number?
A Prime Number is a number which is greater than 1 and divisible by 1 and only itself. Some of the Prime Numbers are 2, 3, 5, 7, 11, 13, 17… In this article, let’s create a Prime Number Program in Python and learn some Optimization techniques.
Prime Number Program in Python
Is 0 a prime number?
0 is neither prime nor composite number, as per the definition, a prime number is a number with exactly two positive divisors, 1 and itself. Zero has an infinite number of divisors (we can divide 0 by all real numbers) Therefore, zero is not a Prime Number.
Is 1 a prime number?
1 is not considered as a Prime because it does not meet the criteria which is exactly two factors 1 and itself, whereas 1 has only one factor
Create a CheckPrime function
We all know that the prime numbers can only be divided by itself and 1.
If the number is less than 1, then it cannot be considered as prime. The idea behind the below code is to scan through all the integers between 2 and number-1, and if anyone of them is the divisor of the number, then the given number is not prime.
We use the modulo division to check if the number is getting divided or not. Modulo division gives us the remainder of the division. If the remainder is zero, then the number is not prime.
def checkPrime(number):
if number < 1:
return False
for i in range (2, number):
if number % i == 0:
return False
return True
number = input("Enter a number to check prime ")
prime = checkPrime(int(number))
if prime:
print(f"{number} is a prime number")
else:
print(f"{number} is not a prime number")
Using While loop
Let’s re-write the above code using the while loop.
def checkPrime(number):
if number < 1:
return False
i = 2
while i < number:
if number % i == 0:
return False
i += 1
return True
number = input("Enter a number to check prime ")
prime = checkPrime(int(number))
if prime:
print(f"{number} is a prime number")
else:
print(f"{number} is not a prime number")
The drawback of this approach is that we need to increment the i variable used in the while loop manually.
Optimization Techniques:
Technique 1: Using Square Root
While checking for Prime, we don’t have to check if the number is divisible by all the numbers till number -1. We can further optimize the above code by adding a simple range change, to check for the divisors up to the square root of the number.
Because for any number, there can be at least two factors, and one of those factors must be smaller than or equal to the square root of the number. If this is not true and both factors were larger than the square root of the number then the resulting number would be larger the number itself.
Let’s take an example 36 and analyze the factors of it, and they are 1, 2, 3, 4, 6, 9, 12, 18.
1 x 36 = 36
2 x 18 = 36
3 x 12 = 36
4 x 9 = 36
6 x 6 = 36
So, we can just iterate till 6 to find out the factors of 36
import math
def checkPrime(number):
if number < 1:
return False
for i in range (2, int(math.sqrt(number))+1):
if number % i == 0:
return False
return True
number = input("Enter a number to check prime ")
prime = checkPrime(int(number))
if prime:
print(f"{number} is a prime number")
else:
print(f"{number} is not a prime number")
Time Complexity of the above algorithm to find factors is O(sqrt(N))
Technique 2: Sieve of Eratosthenes
Sieve of Eratosthenes works on the principle of identifying the smallest prime and eliminating all the multiples of that prime within the range.
Let’s use the Sieve of Eratosthenes approach to find prime numbers between 1 to 25. We need to iterate till the square root of 25, which is 5.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
Since 1 is not a prime, we can remove it.
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
The smallest prime is 2, and start the iteration from 2 to sqrt(number), let’s keep 2 and strikeout all the numbers which are divisible by 2
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
Now the next prime is 3, keep 3 and strikeout all the multiples of 3
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
Since 4 is stricken out, repeat the process with 5
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
Now, all the numbers we have are prime.
[2, 3, 5, 7, 11, 13, 17, 19, 23]
let’s implement Sieve of Eratosthenes in Python
def checkPrime(number):
numbersList = list(range(2,number+1))
for i in range(2,int(number**0.5)+1):
for j in range (i*i, number+1, i):
if j in numbersList:
numbersList.remove(j)
return numbersList
number = int(input("Enter the range to check for prime "))
prime = checkPrime(number)
print(f"******* Prime numbers between 1 to {number} **********")
print(*prime)
Technique 3: Optimized School Method [6n + 1 or 6n – 1]
The Lowest even prime is 2 and the lowest odd prime is 3. Apart from these two numbers all the prime numbers greater than 3 can be expressed in the form of 6n + 1 or 6n -1.
def checkPrime(number):
if number <= 1:
return False
if number == 2 or number == 3:
return True
if number % 2 == 0 or number % 3 == 0:
return False
i = 5
while(i * i <= number):
if (number % i == 0 or number % (i + 2) == 0):
return False
i = i + 6
return True
number = int(input("Enter a number to check for prime "))
prime = checkPrime(number)
if prime:
print(f"{number} is a prime number")
else:
print(f"{number} is not a prime number")
In the above code, we are checking the following conditions
- When the number is less than or equal to 1 then return false as it is not a prime
- Add exclusion for 2 and 3, if the number is 2 or 3 then return true
- If the number is a multiple of 2 or 3 then return false
- The loop starts with 5, which is 6n – 1 and test n % ( i + 2 ) which is 6n + 1
Python Prime Number Generator
To implement the Python prime number generator, we need to get the start and end range from the user and implement Sieve of Eratosthenes to generate all the possible prime numbers with the range.
def checkPrime(start, end):
numbersList = list(range(start, end+1))
for i in range(2,int(end**0.5)+1):
for j in range (i*i, end+1, i):
if j in numbersList:
numbersList.remove(j)
return numbersList
start = int(input("Enter the Starting range "))
end = int(input("Enter the Ending range "))
primeNumberList = checkPrime(start, end)
print(f"******* Prime numbers between {start} to {end} **********")
print(*primeNumberList)
Output:
Enter the Starting range 2 Enter the Ending range 100 ******* Prime numbers between 2 to 100 ********** 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Happy Learning!!
Leave a Reply