11Example programs
Greatest common divisor
Euclid's method, with a while loop and functions that call functions.
The greatest common divisor (GCD) of two numbers is the largest number that divides both. The GCD of 48 and 18 is 6. Long ago, in ancient Greece, Euclid found a fast method to compute it: replace the pair (a, b) with (b, a mod b) until b is zero, and a is the answer.
The least common multiple (LCM), the smallest number both divide into, follows from it: LCM = a / GCD × b.
စံကား
Expected output
ဘုံဆခွဲကိန်း
၆
ဘုံဆတိုးကိန်း
၁၄၄
ဘုံဆခွဲကိန်း
၁
ဘုံဆတိုးကိန်း
၈၅
How it works
ဘုံဆခွဲကိန်း(GCD) runs a while loop as long asခis not zero. Each round it computes the remainder, then shifts the pair along. The parametersကandခare changed in place; that is fine, because parameters are local copies.ဘုံဆတိုးကိန်း(LCM) callsဘုံဆခွဲကိန်းinside a sum. The call is in parentheses so that the division happens before the multiplication. Dividing first keeps the numbers small.နှစ်ခုပြ("show both") has no result. It prints headings and calls the other two.
Tracing GCD(48, 18):
| Round | က | ခ | remainder |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
| end | 6 | 0 |
Hands on
- Print the GCD of 1071 and 462.
- Rewrite
ဘုံဆခွဲကိန်းwith recursion: GCD(a, 0) = a, and GCD(a, b) = GCD(b, a mod b).