Given two integers, the GCD is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 32 and 24 is 8. Our final loop example is probably not suited for all students. It is a great example for a math-oriented teacher with mathematically more mature students. Students should have seen Euclid’s algorithm for finding the greatest common divisor of two integers. Euclid’s algorithm is an efficient method to compute the greatest common divisor. More detail is in http://en.wikipedia.org/wiki/Euclidean_algorithm. Many other good on-line sources exist.
To compute the gcd of 32 and 24 using Euclid’s algorithm:
- Divide 32 by 24 to get a quotient of 1 and a remainder of 8.
- Then divide 24 by 8 to get a quotient of 3 and a remainder of 0.
- 8 is the gcd of 32 and 24.
A program implementing Euclid’s algorithm is given below. It uses a while loop as it is not known how many iterations are needed. The algorithm has found the gcd when b=0.
# 02Loops example_12 GCDWhileLoop.py
# Euclid's algorithm for computing the gcd
a = input('Please input the first integer:')
b = input('Please input the second integer:')
while b != 0:
gcd = b
b = a % b
a = gcd
print(gcd)
The three statements in the while loop are repeated until b becomes 0. The variable a is the dividend and the variable b is the divisor. According to the Euclid’s algorithm, the divisor in the previous step will be the dividend of the next step and the remainder of the previous step will be the divisor in next step. We use the variable gcd to store the divisor. When the variable b becomes 0, the value stored in gcd is the greatest common divisor of the two integers.
A conceptually simpler way for finding the greatest common divisor of two integers a and b is to try out all numbers from 1 to b:
# 02Loops example_12 GCDForLoop.py
# finding the gcd using a "brute force" iteration trying all values
a = input('Please input the first integer:')
b = input('Please input the second integer:')
for i in range(1,b+1):
if a % i == 0 and b % i == 0:
gcd = i
print(gcd)
We divide both a and b by every integer from 1 to b. If both divide by the integer i, set gcd = i. When the loop ends, the value stored in gcd is the greatest common divisor of the two integers. Since 1 is always a common divisor, variable gcd will always have a value when the loop terminates.
