Prime numbers Python, prime number algorithm Python

Let’s create a program on prime numbers in Python using the iterative structures studied so far, in order to deepen them.

So, let’s remember the definition of prime number:

A number is prime when it has only two divisors: one and itself.

So, every natural number greater than 1 that is divisible only by 1 and by itself is prime.

The sequence of prime numbers begins with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …

Algorithm for prime numbers in Python

We have, already, implemented this algorithm in C language: prime number in C. Furthermore, also with Algobuild, we have faced the same topic: prime numbers from 1 to 100 with Algobuild and with Scratch: prime numbers from 1 to 100 with Scratch.

Given a number as input, verify that it is prime.

To implement this algorithm on prime numbers in Python, we take a number as input and divide it gradually by numbers smaller than its half. In fact, it is assumed that dividing a number by values greater than its half, the remainder of the division is different from 0.

Also, since all numbers are divisible by 1, we do without even counting it as a divisor.

So, we set the variable div to 2 and increment it from time to time until we get to number / 2.

If the remainder of the division number % div equals zero, then we count the divisors in a counter variable count initialized to zero.

If the variable count remains at 0 then there are no divisors and therefore the number is prime. Otherwise the number is not prime.

We optimize the algorithm by ending the cycle if the divider reaches half of the number taken into consideration but also if the counter becomes 1, so as not to divide unnecessarily and save much more time. This is especially good for very large numbers.

Here is the complete code of the algorithm for prime numbers in Python:


number = int(input('Enter a number:'))
if number <= 1:
    print('You must enter a number greater than 1')
else:
    div, count = 2.0

while div <= number / 2 and count == 0:
    if number% div == 0:
       count += 1
    div += 1

if count == 0:
    print('Prime number!')
else:
    print('The number is not prime!')

If you want, you can test the code in the online Python compiler in that link: Python compiler online.

We will come back again to propose solutions on prime numbers in Python in the next lessons.

Prev lesson: Python while loop exercises

Next lesson: prime numbers from 2 to N