06.loops.md

Loops

When we write programs, we will very likely run into situations where one instruction or some instructions need to be executed again and again. For example, suppose we need to print hello, world on the screen once every second and keep doing that for one hour. The code below can do this once. If we want to keep printing it for one hour, we would need to write this code 3600 times. Would you like to do that?

import time

print('hello, world')
time.sleep(1)

Note: The built-in time module provides the sleep function, which can pause the program. The argument 1 means the number of seconds to sleep. It can be an int or a float, so 0.05 means 50 milliseconds. We will talk about functions and modules later in the course.

To solve the problem above, we can use loop structures in Python programs. A loop structure is a structure that controls one instruction or some instructions to be executed repeatedly. With such a structure, the code we just saw does not need to be written 3600 times. We write it once, and then put it into a loop structure to repeat it 3600 times. In Python, there are two ways to build loop structures: one is the for-in loop, and the other is the while loop.

for-in Loops

If we clearly know how many times the loop will run, we recommend using a for-in loop. For example, for the situation of repeating 3600 times, we can use the following code. Note that the code block controlled by the for-in loop is also built through indentation. This is the same as how code blocks are built in branching structures. The code block controlled by the for-in loop is called the loop body. Usually, the statements in the loop body are executed repeatedly according to the loop setting.

"""
Print "hello, world" once every second for one hour

Author: Luo Hao
Version: 1.0
"""
import time

for i in range(3600):
    print('hello, world')
    time.sleep(1)

It should be explained that range(3600) in the code above builds a range from 0 to 3599. When we put such a range into a for-in loop, the loop variable i takes out the integers from 0 to 3599 one by one, and this makes the statements in the for-in loop body repeat 3600 times. Of course, range is very flexible. Here are some common examples:

• range(101): generates integers from 0 to 100. Note that it does not include 101.
• range(1, 101): generates integers from 1 to 100. This is like the left-closed, right-open interval [1, 101).
• range(1, 101, 2): generates odd numbers from 1 to 99. Here 2 is the step size, which means the amount added each time. 101 is not included.
• range(100, 0, -2): generates even numbers from 100 down to 2. Here -2 is the step size, which means the amount subtracted each time. 0 is not included.

You may have already noticed that the printing and sleeping in the code above do not actually use the loop variable i. For a for-in loop where the loop variable is not needed, Python convention usually uses _ as the loop variable name. The modified code is shown below. The result does not change, but writing it this way looks more professional.

"""
Print "hello, world" once every second for one hour

Author: Luo Hao
Version: 1.1
"""
import time

for _ in range(3600):
    print('hello, world')
    time.sleep(1)

The code above would run for one hour. If you want to stop the program early, in PyCharm you can click the stop button in the run window, as shown in the picture below. If you run the code in Command Prompt or Terminal, you can use Ctrl+C to stop the program.

Now let us use a for-in loop to compute the sum of the integers from 1 to 100, that is, $\small{\sum_{n=1}^{100}{n}}$.

"""
Sum the integers from 1 to 100

Version: 1.0
Author: Luo Hao
"""
total = 0
for i in range(1, 101):
    total += i
print(total)

In the code above, the role of variable total is to store the accumulated result. During the loop, the value of loop variable i goes from 1 all the way to 100. For each value of i, we execute total += i, which is the same as total = total + i. This statement performs the accumulation. So when the loop ends and we print the value of total, it is the result of adding from 1 to 100, which is 5050. Note that the statement print(total) is not indented. It is not controlled by the for-in loop, so it will not be executed repeatedly.

Next, let us write code to compute the sum of the even numbers from 1 to 100.

"""
Sum the even numbers from 1 to 100

Version: 1.0
Author: Luo Hao
"""
total = 0
for i in range(1, 101):
    if i % 2 == 0:
        total += i
print(total)

Note: In the for-in loop above, we used a branching structure to check whether loop variable i is an even number.

We can also change the arguments of the range function by setting the start value and step size to 2, and use simpler code to compute the sum of the even numbers from 1 to 100.

"""
Sum the even numbers from 1 to 100

Version: 1.1
Author: Luo Hao
"""
total = 0
for i in range(2, 101, 2):
    total += i
print(total)

Of course, an even simpler way is to use Python's built-in sum function. In that case, we do not need a loop at all.

"""
Sum the even numbers from 1 to 100

Version: 1.2
Author: Luo Hao
"""
print(sum(range(2, 101, 2)))

while Loops

If we need to build a loop structure but cannot determine in advance how many times it should repeat, we recommend using a while loop. A while loop uses a Boolean value or an expression that can produce a Boolean value to control the loop. When the value is True, the statements in the loop body, that is, the code block below the while statement with the same indentation, are executed repeatedly. When the value becomes False, the loop ends.

Here is a while loop that computes the sum from 1 to 100:

"""
Sum the integers from 1 to 100

Version: 1.1
Author: Luo Hao
"""
total = 0
i = 1
while i <= 100:
    total += i
    i += 1
print(total)

Compared with the for-in loop, in the code above we added a variable i before the loop starts, and we use this variable to control the loop, so while is followed by the condition i <= 100. In the loop body, besides doing the accumulation, we also need to increase the value of i, so we add the statement i += 1. In this way, the value of i becomes 1, 2, 3, and so on, until 101. When i becomes 101, the condition of the while loop is no longer true, the code leaves the while loop, and then we print the value of total, which is the result of summing from 1 to 100, that is 5050.

If we want to compute the sum of the even numbers from 1 to 100, we can make a small change to the code above.

"""
Sum the even numbers from 1 to 100

Version: 1.3
Author: Luo Hao
"""
total = 0
i = 2
while i <= 100:
    total += i
    i += 2
print(total)

break and continue

What happens if the condition of a while loop is set to True, so that the condition is always true? Let us look at the code below, which still uses while to build a loop structure and compute the sum of the even numbers from 1 to 100.

"""
Sum the even numbers from 1 to 100

Version: 1.4
Author: Luo Hao
"""
total = 0
i = 2
while True:
    total += i
    i += 2
    if i > 100:
        break
print(total)

In the code above, while True builds a loop whose condition is always true. This means that if we do not do anything special, the loop will never end. This is what we often call an infinite loop. To stop the loop after i becomes greater than 100, we use the keyword break. Its job is to terminate the loop. Note that break can only terminate the loop where it appears. This needs attention when using nested loops, and we will soon talk about what nested loops are.

Besides break, there is another keyword that can be used inside loops: continue. It can be used to skip the remaining code in the current round and let the loop directly enter the next round, as shown below.

"""
Sum the even numbers from 1 to 100

Version: 1.5
Author: Luo Hao
"""
total = 0
for i in range(1, 101):
    if i % 2 != 0:
        continue
    total += i
print(total)

Note: In the code above, continue skips the case where i is odd. Only when i is even will the code reach total += i.

Nested Loops

Like branching structures, loop structures can also be nested. In other words, we can build a loop inside another loop. The following example shows how to print a multiplication table.

"""
Print the multiplication table

Version: 1.0
Author: Luo Hao
"""
for i in range(1, 10):
    for j in range(1, i + 1):
        print(f'{i}×{j}={i * j}', end='\t')
    print()

In the code above, the body of the outer for-in loop uses another for-in loop. The outer loop controls the output of row i, while the inner loop controls the output of column j in that row. Clearly, the output of the inner for-in loop is one full row in the multiplication table. So when the inner loop finishes, we use print() to make a line break, so the following output starts again on a new line. The final output is shown below.

1×1=1	
2×1=2	2×2=4	
3×1=3	3×2=6	3×3=9	
4×1=4	4×2=8	4×3=12	4×4=16	
5×1=5	5×2=10	5×3=15	5×4=20	5×5=25	
6×1=6	6×2=12	6×3=18	6×4=24	6×5=30	6×6=36	
7×1=7	7×2=14	7×3=21	7×4=28	7×5=35	7×6=42	7×7=49	
8×1=8	8×2=16	8×3=24	8×4=32	8×5=40	8×6=48	8×7=56	8×8=64	
9×1=9	9×2=18	9×3=27	9×4=36	9×5=45	9×6=54	9×7=63	9×8=72	9×9=81

Applications of Loops

Example 1: Determine Whether a Number Is Prime

Task: enter a positive integer greater than 1 and determine whether it is a prime number.

Tip: A prime number is an integer greater than 1 that can only be divided by 1 and itself. For a positive integer $\small{n}$, we can check whether it has any factor between 2 and $\small{\sqrt{n}}. Of course, the loop does not need to run all the way from 2 to $\small{n - 1}. For positive integers greater than 1, factors appear in pairs, so it is enough to loop until $\small{\sqrt{n}}`.

"""
Read a positive integer greater than 1 and determine whether it is prime

Version: 1.0
Author: Luo Hao
"""
num = int(input('Enter a positive integer: '))
end = int(num ** 0.5)
is_prime = True
for i in range(2, end + 1):
    if num % i == 0:
        is_prime = False
        break
if is_prime:
    print(f'{num} is a prime number')
else:
    print(f'{num} is not a prime number')

Note: In the code above, we use the Boolean variable is_prime. We first assign it the value True, assuming that num is a prime number. Next, we look for factors of num in the range from 2 to num ** 0.5. If we find a factor of num, then it is definitely not a prime number. At this time, we assign False to is_prime, and at the same time use the break keyword to terminate the loop. Finally, according to whether the value of is_prime is True or False, we give different output.

Example 2: Greatest Common Divisor

Task: enter two positive integers greater than 0 and find the greatest common divisor of the two numbers.

Tip: The greatest common divisor of two numbers is the largest one among their common factors.

"""
Input two positive integers and find their greatest common divisor

Version: 1.0
Author: Luo Hao
"""
x = int(input('x = '))
y = int(input('y = '))
for i in range(x, 0, -1):
    if x % i == 0 and y % i == 0:
        print(f'Greatest common divisor: {i}')
        break

Note: In the code above, the loop variable values in the for-in loop go from large to small. In this way, the factor i we find that can divide both x and y is the greatest common divisor of x and y, and then we use break to stop the loop. If x and y are coprime, then the loop will run until i becomes 1, because 1 is a factor of all positive integers. In that case, the greatest common divisor of x and y is 1.

There is an efficiency problem with using the code above to find the greatest common divisor. If the value of x is 999999999998 and the value of y is 999999999999, then clearly the two numbers are coprime and the greatest common divisor is 1. But if we use the code above, the loop will repeat 999999999998 times, which is usually unacceptable. We can use the Euclidean algorithm to find the greatest common divisor, and it can help us get the result much faster. The code is shown below.

"""
Input two positive integers and find their greatest common divisor

Version: 1.1
Author: Luo Hao
"""
x = int(input('x = '))
y = int(input('y = '))
while y % x != 0:
    x, y = y % x, x
print(f'Greatest common divisor: {x}')

Note: The method and steps used to solve a problem can be called an algorithm. For the same problem, we can design different algorithms. Different algorithms differ in storage use and execution efficiency, and these differences show which algorithm is better. You can compare the two pieces of code above and feel why we say the Euclidean algorithm is a better choice. In the code above, the statement x, y = y % x, x means assigning the value of y % x to x, and assigning the original value of x to y.

Example 3: Guess the Number Game

Task: the computer gives a random number between 1 and 100. The player enters the number they guess, and the computer gives the hint A little bigger, A little smaller, or You got it right. If the player guesses the number correctly, the computer tells the user how many times they guessed in total, and the game ends. Otherwise, the game continues.

"""
A small guess-the-number game

Version: 1.0
Author: Luo Hao
"""
import random

answer = random.randrange(1, 101)
counter = 0
while True:
    counter += 1
    num = int(input('Please enter: '))
    if num < answer:
        print('A little bigger.')
    elif num > answer:
        print('A little smaller.')
    else:
        print('You got it right.')
        break
print(f'You guessed {counter} times in total.')

Note: The code above uses import random to import the random module from Python's standard library. The randrange function of this module helps us generate a random number in the range from 1 to 100 (not including 101). The variable counter is used to record how many times the loop runs, that is, how many times the user guessed in total. Each time the loop runs, the value of counter increases by 1.

Summary

After learning branching structures and loop structures in Python, we can solve many practical problems. Through this lesson, everyone should already know that we can use the keywords for and while to build loop structures. If we know in advance how many times the loop repeats, we usually use for loops; if the number of repetitions cannot be determined, we can use while loops. In addition, we can use break inside a loop to terminate the loop, and we can also use the continue keyword inside a loop to let it directly enter the next round.