소인수분해

직관 도입 -- 수를 쪼개보자

약수를 빠짐없이 세거나 두 수의 공약·공배를 고르려면, 그 수를 더 이상 나눌 수 없는 소수들의 곱으로 먼저 적는 편이 빠르다. 소인수분해가 그 적는 법이고, 같은 소인수는 거듭제곱으로 묶는다. 곱의 순서를 바꿔도 소수와 지수가 같으면 결과는 하나다. 각 지수에 1을 더해 곱하면 약수 개수가 나오므로, 수를 소수까지 완전히 나누는 일을 먼저 다룬다.

약수 격자에는 고른 수의 약수가 원으로 찍혀 있고, 그중 소인수는 골드 원으로 구분되어 있다. 인수분해 트리는 수를 아래로 갈라 끝 잎이 모두 소수가 될 때까지 그려져 있다. 같은 소인수가 여러 번 나오면 세로 나눗셈에서 거듭제곱으로 묶고, GCD·LCM 그림에는 두 수의 공통 소인수와 지수의 최솟값·최댓값이 같이 적혀 있다. 슬라이더로 수를 바꾸면 격자·트리·목록이 그 수에 맞게 다시 그려질 뿐, 가지가 화면에서 자라 나가는 것은 아니다.

소인수분해 트리

약수의 개수 구하기

1을 소수로 부르거나, 나누는 순서에 따라 소인수분해가 달라진다고 생각하기 쉽다. 1은 약수가 하나뿐이라 소수도 합성수도 아니고, 가장 작은 소수 2만 짝수이면서 소수다. 같은 수를 어떤 순서로 나눠도 소인수와 지수는 같아지므로 결과는 하나다. 나눗셈을 한 번으로 끝내지 않고 몫이 소수가 될 때까지 이어가야 한다.

최대공약수(GCD)와 최소공배수(LCM) 연결

직접 풀어보기

소인수분해를 할 때는 가장 작은 소수부터 나누고, 몫이 소수가 될 때까지 같은 일을 반복한다. 같은 소수는 거듭제곱으로 묶은 뒤, 약수 개수를 물을 때는 각 지수에 1을 더해 곱한다. 큰 소수부터 나누면 중간에 막히기 쉬우므로 작은 소수부터 확인한다. 이 순서만 지키면 격자에서 본 골드 원과 같은 목록이 나온다.

시험 포인트 정리

소인수와 지수로 적어 두면, 다음 장에서 GCD는 공통 소인수의 지수 최솟값, LCM은 모든 소인수의 지수 최댓값으로 바로 고를 수 있다. GCD×LCM=a×b 관계도 같은 표기 위에 있다. 최솟값과 최댓값을 섞으면 둘이 뒤바뀌므로, 두 수의 소인수 목록을 나란히 놓고 지수를 비교하면 된다.