수학·정수론O(log(min(a,b)))

최대공약수와 최소공배수

유클리드 호제법으로 GCD를 구하고, 곱으로 LCM을 얻어요.

이럴 때 써요

두 수의 최대공약수(GCD)나 최소공배수(LCM)가 필요할 때
분수를 기약분수로 줄일 때 — 분자·분모를 GCD로 나눠요
여러 신호의 공통 주기, 톱니바퀴가 다시 맞물리는 순간처럼 공통 배수를 구할 때

개념

최대공약수는 유클리드 호제법으로 순식간에 구해요. 핵심은 gcd(a, b) = gcd(b, a % b) — 큰 수를 작은 수로 나눈 나머지로 바꿔 가는 거예요. 나머지가 0이 되는 순간의 나눈 수가 답이에요. 한 단계마다 수가 확 줄어서 O(log(min(a, b)))예요.

"gcd(48, 36)" — 나머지가 0이 되면 멈춰요
gcd(48, 36) 을 나머지로 좁혀 가요
gcd(48, 36) :  48 % 36 = 12   →  gcd(36, 12)
gcd(36, 12) :  36 % 12 =  0   →  gcd(12,  0)
gcd(12,  0) :  b 가 0         →  답은 12
→ 최대공약수 12

최소공배수는 GCD만 있으면 바로 나와요. lcm(a, b) = a * b / gcd(a, b) 예요. 두 수의 곱에서 겹치는 부분(GCD)을 한 번 나눠 주는 거예요.

수가 셋 이상이면 누적하면 돼요. lcm(lcm(a, b), c) 처럼 왼쪽부터 접어 나가요. GCD도 똑같이 누적돼요.

패턴 코드

유클리드 호제법으로 GCD·LCM반복문 버전이에요. 재귀로는 return b === 0 ? a : gcd(b, a % b) 한 줄로도 써요.

javascript
Copy code
function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}
function lcm(a, b) {
  return (a / gcd(a, b)) * b;
}

이 유형으로 풀어보기

몫과 나머지정수 나눗셈의 몫과 나머지를 두 언어에서 같은 규칙으로 구해요.쉬움

← 에라토스테네스의 체 소인수분해 →