Practical lesson: functions and Euclid’s algorithm
Finding the greatest common divisor (EKUB) of two numbers by splitting them into prime factors is not handy for a computer; the Euclidean algorithm is short and fast. Its idea: divide a by b and take the remainder, then take (b, remainder) in place of (a, b); repeat until b equals zero, and at the end a is the EKUB. For example (84, 36) → (36, 12) → (12, 0), so EKUB = 12. In Python this is a loop of two lines (code below) – both the swapping and the remainder are done in one line. Once the EKUB is found, reducing a fraction (dividing both parts by the EKUB) and finding EKUK = a * b // EKUB is very easy. The algorithm always stops, because the remainder gets smaller each time and finally reaches zero.
1while b != 0: 2 a, b = b, a % b
A class wanted to cover a rectangular notice board, 48 cm by 72 cm, with identical square pictures and no gaps. The largest possible side is the greatest common divisor of 48 and 72, which is 24 cm, so 6 pictures were needed.
Mathematicians, programmers and accountants simplify fractions to keep sums short and exact.
Find the greatest common divisor of two numbers, such as 36 and 60, on paper by subtraction. Use it to simplify a fraction.
1def ekub(a, b): 2 while b != 0: 3 a, b = b, a % b 4 return a 5print(ekub(84, 36))
12
1def ekub(a, b): 2 while b != 0: 3 a, b = b, a % b 4 return a 5g = ekub(18, 24) 6print(18 // g, 24 // g) 7 8def ekub(a, b): 9 while b != 0: 10 a, b = b, a % b 11 return a 12print(12 * 18 // ekub(12, 18))
3 4 36
“Remainder chain”: pairs choose two numbers, write the chain (a, b) → (b, a % b) in the notebook and find the EKUB; then they check it in a program.