둠선생 연구실

최소공배수는 a * b 를 a와 b의 최대공약수로 나누면 쉽게 구할 수있다. 최대공약수를 찾기위해 유클리드 호제법을 이용하면 쉽다. 유클리드 호제법이란, a 와 b의 최대공약수를 구하기위해 a%b=c를 사용한다. c가 0이라면 b가 최대공약수이고, c가 0이 아니라면 gcd(a,b) = gcd(b,c)를 계산하면 된다. 15와 6의 최대공약수를 구하자면 15%6 = 3이므로 gcd(15,6) = gcd(6,3)과 같고 gcd(6,3)은 6%3 = 0 이므로 3이 최대공약수가 된다. 이를 코드로 구현하면 아래와 같다. int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b); } 추가로 확장 유클리드 알고리즘이 존재하는데, 이는 ax + by = c 에서..