Find the greatest common divisor
Definition
Let a and b be integers not both zero. The largest
integer d such that d|a and d|b is called greatest
common divisor of a and b.
The greatest common divisor of a and b is denoted by
gcd(a,b).
Example
What is the greatest common of 24 and 36?
The positive common divisors of 24 and 36 are 1,2,3,4,6, and 12.
gcd(24,36) = 12
Input
24,36
Output
[1,2,3,4,6,12]
12
Bonus
Euclidean Algorithm to find gcd.
We need a more efficient way to compute the GCD since prime
factorization is very time consuming. It works using the div and mod
operators that we discussed last class. Example gcd(93 , 36)
= gcd(36 , 93 mod 36) = gcd(36 , 21)
= gcd(21 , 36 mod 21) = gcd(21 , 15)
= gcd(15 , 21 mod 15) = gcd(15 , 6)
= gcd(6 , 15 mod 6) = gcd(6 , 3)
= 3.