최대공약수·최소공배수 계산기

이 계산기가 하는 일

쉼표나 공백으로 구분한 정수 두 개 이상을 입력하면 최대공약수(GCD)와 최소공배수(LCM)를 즉시 보여 줍니다. 최대공약수는 목록의 모든 수를 나머지 없이 나누는 가장 큰 정수이고, 최소공배수는 모든 수가 나누어떨어지는 가장 작은 양의 정수입니다. 음수 부호는 무시되고 정수가 아니거나 빈 값은 건너뛰므로, 다소 지저분한 데이터를 붙여넣어도 깔끔한 결과를 얻을 수 있습니다.

그리고 풀이 과정 — 점수는 거기서 나오니까

두 답 아래에는 그 답이 어떻게 나왔는지가 세 가지 방식으로 나옵니다. 소인수분해 표는 각 수를 소수의 곱으로 쓰고(12 = 2² × 3, 18 = 2 × 3²), 최대공약수가 각 소수의 지수 중 가장 작은 것을, 최소공배수가 가장 큰 것을 고르는 모습을 보여 줍니다. 표 하나가 방법 전체이며, 한 번에 50개까지 보여 줍니다 — 그보다 많으면 위의 최대공약수·최소공배수는 그대로 정확하고, 표가 없는 이유를 페이지가 알려 줍니다. 두 수일 때는 유클리드 호제법이 한 줄씩 인쇄됩니다 — 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0 — 마지막에 나눈 수가 답입니다. 마지막으로 공통 약수 전체가 나오는데, 이는 최대공약수의 약수와 정확히 같으므로 목록의 마지막 값이 언제나 위의 답이 됩니다.

답이 아무리 커도 정확하게

수가 많아지면 최소공배수는 빠르게 커지고, 약 9000조를 넘어가면 일반적인 숫자 표현으로는 정확히 담을 수 없습니다. 그래서 이 도구는 최소공배수를 큰 정수로 누적해 그럴듯한 반올림 값이 아니라 정확한 값을 냅니다. 풀이 과정에는 별도의 한계가 있습니다. 인수분해도 약수 훑기도 전부 시행 나눗셈이기 때문입니다. 약 1조를 넘는 수는 소인수분해 표에서 제외되고, 표는 한 번에 50개까지만 만들며, 최대공약수 자체가 1조를 넘으면 공통 약수 목록은 건너뜁니다. 각각을 조용히 지우지 않고 이유와 함께 알려 줍니다 — 이 한계가 없을 때는 붙여넣은 1MB의 숫자가 키 입력마다 화면을 30초 넘게 멈추게 했습니다.