소인수분해로 최대공약수 구하기

수가 커지면 약수를 나열하는 데 시간이 오래 걸리지만, 소인수분해를 하면 더 빠릅니다. 두 수를 모두 소인수분해해 보세요. 45는 3 × 3 × 5이고 75는 3 × 5 × 5입니다. 두 수에 공통으로 있는 소수는 3 하나와 5 하나입니다.

공통 소수들을 곱하면 3 × 5는 15이며, 45와 75의 최대공약수입니다. 소수는 두 수 모두에 나타나는 횟수만큼만 공통으로 셉니다. 45에는 3이 두 개 있지만 75에는 하나만 있으므로 3은 하나만 포함합니다.

작동 원리: 공통 인수는 두 수에 모두 포함된 소수로만 만들 수 있습니다. 공통 소수를 두 수가 허용하는 만큼 모두 취하면 가장 큰 공통 인수가 만들어집니다. 지수를 고려할 때는 각 공통 소수의 지수가 더 작은 쪽을 취합니다. 3^2 × 5와 3 × 5^2는 3 × 5가 됩니다.