소인수분해로 최소공배수 구하기

소수는 최소공배수(LCM)를 구할 때도 쓰입니다. 두 수를 소인수분해해 보세요. 20은 2^2 × 5이고 30은 2 × 3 × 5입니다. 20의 배수에는 2가 두 개와 5가 하나 있어야 하고, 30의 배수에는 2, 3, 5가 각각 하나씩 있어야 합니다. 이 모든 소인수를 포함하는 가장 작은 수를 구하려면 각 소인수를 가장 많이 필요한 횟수만큼 취하면 됩니다.

즉 2가 두 개, 3이 하나, 5가 하나입니다. 2^2 × 3 × 5는 60입니다. 따라서 20과 30의 최소공배수는 60입니다. 확인해 보세요. 60 / 20은 3이고 60 / 30은 2입니다.

최대공약수와 비교해 보세요. 최대공약수는 공통 소수만 남기고, 각 소수의 지수는 더 작은 지수로 합니다. 최소공배수는 나타나는 모든 소수를 포함하고, 각 소수의 지수는 더 큰 지수로 합니다. 하나는 둘 다 가진 것만 남기고, 다른 하나는 둘 중 하나가 필요로 하는 것까지 확장합니다.