Greatest Common Divisor
Calculate the greatest common divisor fo two positive integers.
Input: Two positive integers.
Output: The greatest common divisor.
The greatest common divisor GCD(a, b) of two positive integers a and b is the largest integer d that divides both a and b.
Input format: Two integers a and b separated by a space.
Output format: GCD(a, b).
Example:
Input:
3918848 1653264
Output:
61232
Naive algorithm
GCD(n):
best <- 0
for d from 1 to a+b:
if (d/a and d/b):
best <- d
return best
Fast algorithm
euclidGCD(a, b):
if b = 0:
return a
aPrima <- the reminder when a is divided by b
return euclidGCD(b, aPrima)
Python implementation
def euclidGCD(a, b):
if b == 0:
return a
aP = a % b
return euclidGCD(b, aP)