In the previous Python lesson we studied prime numbers, here is the link of the lesson. Now we will develop a Python algorithm for prime numbers from 2 to N.
Python prime numbers from 2 to N
Write a Python program that determines prime numbers from 2 to N.
Let’s start thinking about a possible solution.
Since it is a complex problem we can divide it into sub-problems to be able to better find the solution.
First step: determine if a number is prime
To find a prime number just divide it by the numbers below it and count the divisors. If there are only two, that is, 1 and itself, then the number is prime, otherwise it is not.
But we can do without dividing by a number larger than its half, as it is assumed that it will always give a number with a comma.
It is also discounted with a number that is divisible so we can start dividing from the number 2.
We then use the variable div which is used for the divisor initialized to 2. Div is then increased by one for each iteration until it reaches half the number (N / 2).
We also use the variable count to count the number of divisors. If the number taken as input divided by div gives the remainder 0, the variable count, initialized to zero, is incremented.
Python prime numbers from 2 to N – Here is the portion of code we thought about:
N = int(input('Enter the interval N: '))
div, count = 2.0
while div <= N / 2:
if N % div == 0:
count += 1
div += 1
But in the case of very large numbers this would take a long time. Then we can improve the algorithm by terminating the iterations as soon as the count becomes 1, since already with a divisor the number cannot be prime.
So let’s modify the while like this:
while div <= N/2 and count == 0: …
You can test the code in the online Python compiler in that link: Python compiler online.
Second part – Prime numbers from 2 to N
Now we need to display the prime numbers in a range, from 2 to N.
For example, if we take N = 10, the prime numbers in the interval are: 2,3,5 and 7.
To do this we therefore ask to take a number N as input and using another external while loop we begin to check if N is prime. If it is we will print it, otherwise not. Then we decrease N until we reach 2 then we set the condition N > 1.
Here is the complete code:
N = int(input('Enter the interval N:'))
while N > 1:
div, count = 2.0
while div <= N / 2 and count == 0:
if N % div == 0:
count += 1
div += 1
if count == 0:
print(N)
N -= 1
N.B. Instead of using the and inside the condition, I could use the break statement after finding the first divisor. Later in the tutorial I will explain how to use it.
if N % div == 0:
count += 1
break
Conclusion
In this lesson we have developed a Python algorithm for prime numbers from 2 to N, in the next lessons we will develop other interesting algorithms.
Some useful links
How to find the maximum of N numbers