[알고리즘] 유클리드 호제법 in Java (최대공약수, 최소공배수)

1. 최대공약수를 구하는 유클리드 호제법

유클리드 호제법(Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(the greatest common denominator, GCD)를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 

 

2개의 자연수(또는 정식) a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

이 성질에 따라 b를 r로 나눈 나머지 r' 를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다. 아니....기원전 300년....?????대박사건....

 

2. 소스코드 in Java

public static int gcd(int p, int q) {
    if(q == 0) return p;
    return gcd(q, p%q);
}

 

3. 최소공배수 공식

p, q 두 수의 최소공배수(the least commin multiple, LCM)를 구하는 공식은

p*q/gcd(p, q)

 

https://programmers.co.kr/learn/courses/30/lessons/12940

최대공약수와 최소공배수 문제를 풀다가 알게된 알고리즘. 

기원전 300년 경에 쓰였다니...놀라울 따름이다....

코딩테스트 연습 - 최대공약수와 최소공배수

ref: https://ko.wikipedia.org/wiki/유클리드_호제법