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.
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.
In this lesson we will study indefinite loop in Python, that is loops where the number of iterations is not known at the beginning of the loop.
Let’s take some examples to better understand what is meant by an indefinite cycle.
Indefined loop in Python – first example
Insert integers and add them, exit the program when entering the zero value.
First we ask you to enter an integer n as input. After we set the variable sum equal to n and we carry out a loop to insert the other numbers and add them.
We set the condition n! = 0 in the while so as to stop the loop only if the value zero is entered.
Finally we display the sum obtained.
Here is the complete code on indefined loop in Python:
print('Enter numbers, enter 0 to finish!')
n = int(input('Insert a number: '))
sum = n
while n != 0:
n = int(input('Insert a number: '))
sum += n
print('The sum is: ', sum)
As you may have noticed, this time the cycle will end when we decide to stop, by entering the number 0 in this case. You may need to enter any other value.
In this lesson we will make a program on friendly numbers in Python, in order to practice with iterative structures.
Recall that two numbers are said to be friendly if the sum of the divisors proper to one, but excluding the number itself, is equal to the other number and vice versa.
For example, numbers 220 and 284 are friendly.
In fact, the divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110. Their sum gives me 284.
Similarly we find the divisors of 284: 1, 2, 4, 71, 142 which sum makes 220.
So the numbers are friendly.
Friendly numbers – algorithm in Python
The solution algorithm therefore consists in finding all the divisors of the first number, excluding the number itself, adding them and comparing them with the other number. Similarly with the second number.
So first of all we take the two integers as input and store them in two variables number_one and number_two. Then we initialize the variables div, sum1 and sum2.
The variable div represents the divisor and is initialized to 1 at the beginning and after the first while, because we will need it for the other number. Alternatively, another variable could be used.
After with the while loop we find all the divisors of the number_one and add them in the variable sum1. The same for the other number for which we add the divisors in the variable sum2.
Finally we compare sum1 with number_two and sum2 with number_one. If both equalities are true then the numbers are friendly, otherwise they are not.
Here is the complete code of the algorithm on friendly numbers in Python:
number_one = int(input('Enter the first number:'))
number_two = int(input('Enter the second number:'))
div, sum1, sum2 = 1,0,0
while div <= number_one / 2:
if number_one % div == 0:
sum1 += div
div += 1
div = 1 # let's return the divisor to 1
while div <= number_two / 2:
if number_two% div == 0:
sum2 += div
div += 1
if sum1 == number_two and sum2 == number_one:
print ('The numbers are friendly!')
else:
print ('The numbers are not friendly!')
We could add a check, because in fact it is useless to find all the divisors of the second number, if sum1 is different from number2.
Therefore it would be appropriate to find the divisors of the second number only if the condition sum1 equal to number_two is satisfied.
In this lesson we will develop the Euclidean algorithm in Python.
Euclid’s algorithm is a method used to find the greatest common divisor between two integers.
By greatest common factor, GCD, between two integers we denote the greatest common divisor of both.
Euclidean algorithm consists in dividing the two numbers and considering the remainder. The procedure ends when the remainder is found equal to zero.
Let’s take some examples.
Euclidean algorithm Python – First example
Let’s take two numbers for example 20 and 15 and proceed according to Euclid’s algorithm.
First pass: a / b i.e. 20/15 = 1 remainder 5 – the remainder is non-zero, so I keep dividing.
The second step will thus be, exchanging a with b and b with r, that is 15/5 = 3 remainder 0.
We found the remainder equal to zero, so the GCD is 5.
Euclidean algorithm Python – Second example
Let’s create a second example in order to understand how Euclid’s algorithm works.
So let’s take the numbers 64 and 30.
64/30 = 2 remainder 4 – the remainder is non-zero, so we keep dividing.
30/4 = 7 remainder 2 – the remainder is non-zero, so we keep dividing.
4/2 = 2 remainder 0
The remainder is zero, so the GCD is 2.
Euclidean algorithm in Python
Let’s now implement this algorithm in Python.
First of all we take as input the two numbers a and b. Then as long as b is greater than 0, we calculate the remainder of the divison of a divided by b and exchange a with b and b with r. So let’s print a.
So here is the complete code that represents the Euclidean algorithm in Python:
a = int(input('Insert the first number: '))
b = int(input('Insert the second number: '))
while b > 0:
r = a % b
a, b = b, r
print (a)
You can also test the code in the online Python compiler in that link: Python compiler online.
This is a possible implementation of the Euclidean algorithm, in the next lesson we will do other examples on loops in Python.
The append method in Python, discussed in the last lesson, is used to insert items at the end of a list.
The syntax of this method is as follows:
list.append (element)
The method accepts only one parameter, the element to be inserted in what to the list.
First exercise with append in Python
There is no better way to learn something than through practice. So let’s do some exercises.
Populate a list of n keyboard integers. At the end of the insertion with another cycle, select one element out of three and add them. Finally, display the sum as output.
So first of all we ask you to enter the number of elements, that is n.
Next, we declare the empty list named integers and initialize the sum to zero.
With a for loop we insert the elements in the list and then with another for loop a step of 3 we select an element every 3.
So we display the sum in output.
So here’s a possible solution using Python’s append method:
n = int(input('How many numbers do you want to enter?: '))
numbers_int = []
s = 0
for i in range(n):
number = int(input('Insert a number: '))
numbers_int.append(number)
for i in range(0,n,3):
s += numbers_int[i]
print(s)
Second exercise with append in Python
Let’s do a second exercise again using append method.
Enter 20 random numbers from 10 to 100 with a for loop. Then check with another cycle how many values greater than 50 have been entered.
We set the number of elements ie n to 20. Then we initialize the random list to the empty list and add it to 0.
Then with a for loop that goes from 0 to n-1, we fill the list with random values from 10 to 100. For this purpose we use the randint function, of the random module, which generates random numbers among the values set inside the round brackets.
Then with a for loop we calculate how many values greater than 50 have been generated and finally we display the result in output.
So here’s the complete code using append method in Python:
import random
n = 20
numbers_random = []
count = 0
for i in range(n):
number = random.randint(10,100)
numbers_random.append(number)
for i in range (n):
if(numbers_random[i] > 50):
count += 1
print(count)
In these exercises we used the append method in Python to insert items at the end of a list, in the next lessons we will deepen this method again.
Commenti recenti