소인수분해·최대공약수·최소공배수

소인수분해부터 최대공약수·최소공배수까지

소인수분해는 자연수를 소수들의 곱으로 나타내는 것이에요. 360 = 2³ × 3² × 5처럼, 어떤 순서로 나누든 결과는 하나뿐이에요(산술의 기본 정리). 수를 하나 넣으면 작은 소수부터 차례로 나누는 나눗셈 사다리와 함께 소인수분해 결과를 보여 주고, 약수의 개수((지수+1)의 곱)와 약수의 합, 약수 목록도 알려 줘요. 약수가 1과 자기 자신뿐이면 소수라고 표시해요.

최대공약수와 최소공배수 구하는 세 가지 방법

• 공약수로 나누기 — 모든 수를 함께 나눌 수 있는 소수로 계속 나눠서, 왼쪽에 나온 수를 곱하면 최대공약수, 여기에 아래에 남은 수를 곱하면 최소공배수예요(두 수일 때).
• 지수 비교 — 각 수를 소인수분해해서 소인수마다 가장 작은 지수를 고르면 최대공약수, 가장 큰 지수를 고르면 최소공배수예요. 세 수 이상일 때 가장 편해요.
• 유클리드 호제법 — 큰 수를 작은 수로 나눈 나머지로 다시 나누기를 되풀이해서, 나머지가 0이 될 때 나누는 수가 최대공약수예요. 큰 수에서도 아주 빨라요.

큰 수도 계산해요

작은 소인수는 하나씩 나눠 보고, 남은 큰 수는 밀러–라빈 소수 판정과 폴라드 로 알고리즘으로 나눠서 24자리 수까지 기기 안에서 바로 소인수분해해요. 모든 계산은 큰 정수(BigInt)로 해서 자릿수가 많아도 반올림 오차가 없어요. 수 사이는 쉼표나 띄어쓰기로 나눠요(천 단위 쉼표는 쓰지 말아 주세요).

참고한 자료

• SymPy factorint · gcd · lcm (결과 대조에 쓴 기준)