수학

최대공약수

유클리드가 2300년 전에 푼 문제

바닥에 타일을 빈틈없이 깔아 보세요. 정사각형 타일만 쓰고 한 줄씩 가장 큰 것으로 깝니다.

나머지가 0 이 되면 끝난다

• 더 놓을 칸이 없는 줄 — 정사각형이 바닥을 딱 채우면 나머지가 0 이다. 그 줄의 정사각형 한 변이 답이다
• 빈틈없이 채우는 정사각형 — 한 변 3 짜리로도 깔 수 있지만 가장 큰 것은 6 이다. 가장 큰 것 = 최대공약수
• 그래서 — 가장 큰 정사각형으로 깔면 한 줄마다 바닥이 확 줄어든다

코드는 나머지를 넘겨 주는 한 줄이 전부다

다음을 눌러 한 줄씩 넘기며 바닥이 줄어드는 걸 보세요. 처음 화면은 ①에서 깐 48×18 입니다. 아래 버튼으로 다른 두 수도 돌려 볼 수 있습니다.

48과 18 의 최대공약수는 6 입니다. 나머지를 3번 구하면 끝납니다.

• while b — 나머지가 0 이 아닌 동안 계속한다. 바닥이 남아 있다는 뜻이다
• a, b = b, a % b — 짧은 변이 새 긴 변이 되고 나머지가 새 짧은 변이 된다
• return a — b 가 0 이 되면 그때의 a 가 최대공약수다

최대공약수에서 틀리는 자리

• 실전에서는 — math.gcd(a, b) 한 줄이다. 여러 수도 math.gcd(48, 36, 24) 로 12 가 나온다
• 최소공배수는 — a * b // gcd(a, b) 로 구한다. 84 와 36 이면 252 다. / 를 쓰면 252.0 처럼 실수가 나온다
• 작은 수가 앞에 와도 — 틀리지 않는다. gcd(18, 48) 은 첫 반복에서 (48, 18) 로 자리가 바뀐 뒤 6 이 나온다
• 0 이 들어오면 — gcd(12, 0) 은 12, math.gcd(0, 0) 은 0 이다
• 기약분수는 — 분자와 분모를 gcd 로 나눈다. 18/48 은 gcd 가 6 이라 3/8 이다
• 약수를 하나씩 찾으면 — 1천만 근처의 두 수에서 0.54초, 유클리드는 0.0000002초다(Python 3.14, 컴퓨터마다 다르다)

문제에서 이 말이 보이면

다음 장에서는 소수를 체로 거르는 에라토스테네스의 체를 봅니다.