GCD(Greatest Common Divisor) & LCM(Least Common Multiple) 1. Find GCD of two number Method 1: use basic Euclidean algorithm. GCD(a, b) = GCD(b%a, a) Method 2: use extended Euclidean algorithm. GCD(a, b) = ax + by Let values of x and y calculated by the recursive call be x 1 and y 1 x = y 1 - ⌊b/a⌋ * x 1 y = x 1 2. Find LCM of two number LCM(a, b) * GCD(a, b) = a * b 3. Reference http://www.geeksforgeeks.org/mathematical-algorithms/#gcd
댓글
댓글 쓰기