[도구정리]최대공약수, 최소공배수(GCD, LCM)

유클리드 호제법을 이용한 방식이다.

a-bq가 서로소인 이유는 귀류법을 사용하여 증명하면 된다. 둘 사이에 공약수 p가 있다고 가정하고 진행하면 a,b가 공약수를 가지면서 모순이 된다. 

 

LCM은 더욱 간단하다. 최소 공배수이기때문에 서로소인 a,b를 모두 갖고 있어야하고 a와 b에도 서로소인 d또한 갖고 있어야 한다.

즉 최소공배수는 a*b*d가 된다.

 

코드를 보면 다음과 같다.

	public static int gcd(int a, int b){
        if(b == 0) return a;
        return gcd(b, a % b);
        }

 gcd코드이다. 두 숫자를 받아 나머지를 찾는 방식으로 진행된다. 그러다 나머지가 나오지 않는 -> 즉 공약수가 처음 생기는 지점에서 그 값을 반환시키며 재귀 함수 호출을 마친다.

    public static int lcm(int x, int y) {
 
        //0이 아닌 두 수의 곱 / 두 수의 최대공약수
        return (x * y) / gcd(x, y);
    }

LCD의 경우에 두 수의 곱을 먼저 구해준다. 이 경우 a*b*d*d가 되기 때문에 gcd를 통해 두 수의 최대 공약수를 한번 나누어 계산을 마친다.