Given two integers a and b, it finds the largest integer that divides both of them, known as their greatest common divisor (gcd).Algorithm for gcd was discovered well over 2000 years ago by the mathematician Euclid, in ancient Greece.
Euclid's rule
If x and y are positive integers with x >= y,then gcd(x,y) = gcd(x mod y,y).
pseudo code
function Euclid(ab)
Input: Two integers a and b with a b 0
Output: gcd(ab)
if b = 0: return a
return Euclid(b,amod b)
Euclid's rule
If x and y are positive integers with x >= y,then gcd(x,y) = gcd(x mod y,y).
pseudo code
function Euclid(ab)
Input: Two integers a and b with a b 0
Output: gcd(ab)
if b = 0: return a
return Euclid(b,amod b)
No comments:
Post a Comment