Prime numbers program in python

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.

is a number prime or not example
Is a number prime or not?

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.

first n prime numbers example
First n prime numbers example.

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: