[디폴트코드] 최소공배수, 최대공약수

최대 공약수 GCD

유클리드 알고리즘을 사용하면 쉽게 구할 수 있다.

• 2개의 자연수 A, B에(A>B) 대해서 A를 B로 나눈 나머지를 r이라 하면, A와 B의 최대공약수는 B와 r의 최대공약수와 같다.
• 이 성질에 따라, B를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
• java 코드로 작성하면 다음과 같다. (A보다 B가 커도 된다.)

static int gcd(int a, int b) {
		while (b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

최소 공배수 LCM

두 수 A,B를 곱한 값을 최대공약수로 나눈 값이다.

static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}