Chapter 8
While loops allow programs to repeat without necessarily knowing ahead of time how many times the loop will run. Like selection, this allows programs to adapt and run more or less code, depending on the circumstances.
Consider the task of printing a table of prime numbers. An integer n is prime if it is greater than 1 and its only positive divisors are 1 and itself. This definition leads to the following program:
Listing 8.1: Prime Numbers
1 # primes.py
2
3 def isprime(n):
4 # Return True if n is prime.
5 return n > 1 and smallestdivisor(n) == n
6
7 def smallestdivisor(n):
8 # Find smallest divisor (other than 1) of integer n > 1.
9 k = 2
10 while k < n and not divides(k, n):
11 k += 1
12 return k
13
14 def divides(k, n):
15 # Return True if k divides n.
16 return n % k == 0
17
18 def main():
19 for n in range(2, 100):
20 if isprime(n):
21 print(n, end=" ")
22 print()
23
24 main()
The definition of the isprime() function parallels the definition of prime number in a nice way and reads like pseudocode. In addition to the while loop, this program uses the modulus operator % and the end= option of print() for the first time.
The syntax of a while loop is almost identical to that of an if statement.
while <boolean>:
<body>
The <boolean> expression is evaluated, and if it is True, then <body> is executed. (So far, this is identical to an if statement.) After the body executes, <boolean> is evaluated again, and if it is still True, then the body executes again. This is repeated until the boolean expression is False.
Unlike a for loop, it is distinctly possible for a while loop to be infinite. Use CTRL-C or look for an option to restart your interpreter or shell if you execute an infinite loop.
The modulo or mod operation finds the remainder when one integer is divided by another.
n % m |
Remainder when n is divided by m. |
So, for example, k divides n evenly if the remainder is 0; i.e., if n % k == 0.
The Python print() function has two options that give you somewhat more control over output:
print(..., end=s) |
Print with string s at end instead of newline. |
print(..., sep=s) |
Print with string s between expressions. |
Both options may be set at the same time.
You may have found it hard to follow exactly what is happening in Listing 8.1. One reason might be its use of several functions, another could be the while loop in smallestdivisor(). Tracing code by hand can help overcome both of these difficulties. When we trace code by hand, we try to simulate on paper what the interpreter is asking the CPU to do.
For example, we might trace the evaluation of isprime(9) like this:
isprime(9)
→ smallestdivisor(9)
→ divides(2, 9) returns
→ divides(3, 9) returns
returns
returns
To follow the operation of smallestdivisor(), it may also be helpful to track the values of its variables, like this for the call smallestdivisor(25):
There is nothing special about these ways of writing the traces; the point is just to find a helpful way of simulating the program’s execution.
Although it is not immediately obvious, Listing 8.1 runs its while loop inside of another loop—the for loop in main(). That means the entire while loop from smallestdivisor() runs once every time the body of the for loop runs.
Any time one loop is run inside of another loop, the loops are called nested. As you may imagine, nested loops can have a significant impact on program performance.
for i in range(4):
print(i)
for j in range(3):
print(j)
for i in range(4):
print(i)
for j in range(3):
print(j)
def divides(k, n):
if n % k == 0:
return True
else:
return False
Discuss the tradeoffs between writing the function in this way compared with the original version.
Replace m with n, and n with m % n until n is 0.
Once n becomes 0, the gcd is in m. Write a program gcd.py with a main() that uses nested loops to test your function thoroughly.
3.131.38.210