유클리드 호제법

유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 가장 오래되고 효율적인 알고리즘 중 하나이다.

기본 원리는 "두 수 a, b가 있을 때(a>b), a를 b로 나눈 나머지 r에 대하여, a와 b의 최대공약수는 b와 r의 최대공약수와 같다"는 성질을 이용하는 것이다.

시간복잡도: $O(log(min(a,b)))$

최소공배수(Least Common Multiple) 공식

$a * b / GCD$

문제

백준 13241번 최소공배수

풀이

b가 0이 될 때까지 반복하는 이유는 공통으로 채울 수 있는 제일 큰 벽돌을 찾기 위해 나머지가 0일 때 까지 하는 것이다.

import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		
		long atemp = a;
		long btemp = b;
		
		//유클리드 호제법으로 GCD 구하기
		while(b != 0) {
			long r = a % b;
			a = b; //큰 수를 작은 수로 교체
			b = r; //작은 수를 나머지로 교체
		}
		
		long gcd = a; //b가 0이 되었을 때의 a가 최대공약수
		
		long lcm = atemp * btemp / gcd;
		
		System.out.println(lcm);
	}
}