코테연습중 최대공약수와 최소공배수의 문제를 풀때 해당 공식을 이해하고 기억하면 좋을 것 같아서 작성하게 되었습니당!

최대공약수 (GCD, Greatest Common Divisor)

두 자연수의 공통된 약수

구하는방법

예를 들어 10, 15과 주어진다고 가정했을때

10의 약수 : 1, 2, 5, 10
15의 약수 : 1, 3, 5, 15
공통되는 약수는 1, 5이기 때문에 최대공약수는 5가 됩니다.

이를 알고리즘으로 풀려면 유클리드 호제법을 알고 있어야 합니다.

1. 유클리드 호제법

x, y 의 최대공약수는 y, r 의 최대공약수와 같다. (여기서 r은 x%y 입니다.)

계속해서 x 값에는 y 값을 대입하고 y 값에는 r 값을 대입하다보면 언젠가는 r 이 0 이 되는데 이때에 y 값에 있는 값이 최대공약수 입니다.

위에 그림처럼 10과 15가 있을 때 계속적으로 대입하고 나누다보면 y 가 5일 때 r 이 0이 되기때문에 최대공약수는 5가 됩니다.

이를 재귀함수를 이용하여 코드로 나타내면 아래와 같습니다.

재귀함수

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

최대공배수(LCM)

두 자연수의 공통된 배수 중 가장 작은 수

최대공배수: 두 수를 곱한 값/최대공약수

최대공배수는 최대 공약수만 구하면 구하기가 매우매우 쉽습니다!!!😁

작성하게 만든 알고리즘 문제(프로그래머스)

최대공약수와 최소공배수

Reference

최대공약수와 최소공배수

[알고리즘] 최소공배수, 최대공약수와 유클리드 알고리즘