Repetition in Python: Loops That Are Nested

Just as it is possible to have if statements nested within other if statements, it is possible, and even likely, to have a loop nested within another loop. An ex­ample of nested for loops is as follows:

for i in range(0, 10)

for j in range (0,  10)

print (i,j)

The print statement in this example executes 100 times. Each time the outer loop executes once, the inner one is executed 10 times, for a total of 10 * 10 or 100 iterations. Loops can be nested to a greater depth if necessary, and while and for loops can be nested interchangeably.

Since there was a discussion of prime numbers and factoring, consider the problem of finding the number within a given range that has the greatest number of different factors. Leaving out 1 and the number itself, 2 has no factors, nor does 3; 4 has one (=2), 5 has none, and 6 has two (2 and 3). Which number be­tween 0 and 1000 has the most?

From the prime number game, it is clear that the factors can be found using a loop. If the loop is not exited when one is found, all of them can be identified and, more importantly for this problem, counted. For a given number k, the factors can be identified using the following loop:

count = 0;

for n in range (1, int(k/2)): # Divide K by all numbers < K/2

if k%n == 0:  # If the remainder is 0 then n

count = count + 1

# The number k has count numbers that divide evenly into it.

The statement count = count + 1 has replaced the isprime = “no” statement from the prime number game. When the loop ends, the value of count is the number of divisors it has. If this number is 0, then the number k is prime. The problem has been solved for any number k. Now solve it for all numbers between 1 and1000 and identify the number with the largest value of count (i.e., the larg­est number of divisors). This involves another loop enclosing this one that counts from 1 to 1000.

Define a variable maxv which is, at any given moment, the number that has the greatest number of divisors, and another variable maxcount, which is the number of divisors that maxv has. Initially maxv is 1 and maxcount is 0 (i.e., the number 1 has no divisors). Now loop between 1 and 1000 and replace maxv and maxcount whenever a new number is found for which the number of divisors is greater than maxcount. Specifically,

maxv = k                   # and the value itself

print (“The most divisors is “,maxv,” with “,maxcount)

The result for 1 to 1000 is as follows:

The most divisors is 840 with 30

The result for 1 to 10000 is as follows:

The most divisors is 7560 with 62

This last version needs 10 seconds to execute.


Source: Parker James R. (2021), Python: An Introduction to Programming, Mercury Learning and Information; Second edition.

Leave a Reply

Your email address will not be published. Required fields are marked *