Creating a prime numbers program in python is a popular exercise to practice loops. One of the reasons is that “prime number” is a well-defined concept in mathematics.
Because of that, there are no ambiguities when we consider if a number is prime or not.
Condition for a prime number
Let’s examine when a number is a prime.
A prime number is an integer number greater than 1, that has only two divisors: 1 and itself.
So, if a number has a divisor between 2 and the number -1, then we can conclude the number is not prime. When a number is not prime, we say the number is composite.
There is a fact that we can use if we look closer at the divisors.
Let’s assume s is the square root of n, this means that n = s*s.
So, if n has a divisor greater than s, then it will also have a divisor that is less than s.
Therefore, we only need to look for divisors until the square root of the number. To be more precise, from 2 to the integer part of the square root of a number.
See the following example.
n = 32
The integer part of the square root of 32 is 5. 5×5=25, 6×6=36
16 is a divisor of 32 because 16×2=32
That is, 16 > 5, but there has to be a number (2) that is less than the square root that multiplied by 16 equals 32.
Prime number function in Python
Let’s see the python function to determine whether a number is prime or not.
As a rule of thumb for me, I only use include a Python module when is necessary, I mean, when there is no other way, I can do the same without that module.
In particular, the square root is a function that is included in a module named math.
But, we know from mathematics, that the square root of a number equals the number to the power of ½. So, I’m going to use that, so I don’t need to import an extra module.
def is_prime(n):
square_root = int(n**0.5) + 1
for i in range(2, square_root):
if n % i == 0:
return False
return True
Notice from the implementation of the function is_prime, that if we find 1 divisor is enough to conclude that the number is not prime.
If the loop is executed in full, it means that we never find a divisor, so we can return that the number is prime.
In the loop, we need to add +1 to the range, because in python, if the loop is from 2 to 2, it won’t execute the block of instructions. In other words, it won’t go inside of the loop.
You can write a main program to test the function as follows:
if __name__=='__main__':
n = int(input('Enter a number greater than 1: '))
if n>1:
print('It is prime') if is_prime(n) else print('It is not prime')
Something else you can do here if you want to test several numbers is to create a menu for the console application that asks the user if he/she wants to test another number.
To practice, even more, you can exception handling to the previous code.
Why?
Execute the main program above and instead of a number, input a letter, you will see what happens.
Finding prime numbers in a range
Another common example of a prime numbers program in python is finding prime numbers in a range.
We will use the function is_prime, and look for prime numbers in a range that the program will receive as input.
Find the code below.
def find_primes_on_range(lower_bound, upper_bound):
for number in range (lower_bound, upper_bound):
if is_prime(number):
print(number, ' is prime')
And you can test this code with the following main program.
if __name__=='__main__':
lower_bound = int(input('Enter the lower bound of the range: '))
upper_bound = int(input('Enter the upper bound of the range: '))
find_primes_on_range(lower_bound, upper_bound)
Finding the first n prime numbers
As the final example, let’s see how we can print the first n prime numbers.
def first_n_prime_numbers(n):
for number in range(2, n):
if is_prime(number):
print(number, ' is prime')
And you can test the function with the main program below.
if __name__=='__main__':
n = int(input('First n prime numbers, enter n: '))
if n>1:
first_n_prime_numbers(n)
H@ppy coding!
Related posts: