[공식] 최대공약수,최소공배수 / 유클리드 호제법

유클리드 호제법

: 두 개의 자연수에 대한 최대공약수(GCD:Greatest Common Divisor)를 구하는 대표적인 알고리즘

개념

• 두 자연수 A,B에 대해서 A>B일 때, A를 B로 나눈 나머지를 R이라고 한다. (R=A%B)
• 이 때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
• 위의 B와 R은 각각 A와 B가 되고, 또 A를 B로 나눈 나머지가 R이 된다.
• 위의 과정을 반복하다가, A를 B로 나눈 나머지 R이 0이 되는 순간의 B값이 최대공약수이다.

예시

코드

int gcd(int a, int b) {
	// a>b라고 가정
	if (a%b==0) return b;
    else return gcd(b,a%b);
}

(+) 최소 공배수 구하기

두 자연수 A와 B에 대해서,

• A와 B의 최소공배수는 A와 B의 곱을 두 수의 최대공약수로 나눈 것과 같다.