2소인수분해

 

어떤 정수를 소수의 곱만으로 표현하는 것을 소인수분해라고 합니다.

예를 들어 12를 소인수분해하면 2*2*3이 됩니다. 왜 이렇게 되는지 소인수분해 과정을 단계별로 풀어보면 다음과 같습니다.

 

1 | 12를 가장 작은 소수인 2로 나눕니다.

2 | 12는 2로 나누어지므로 2는 소인수입니다(2를 출력합니다).

3 | 12를 2로 나눈 몫인 6을 대상으로 다시 생각합니다.

4 | 6을 2로 나눕니다.

5 | 6은 2로 나누어지므로 2는 다시 소인수에 포함됩니다(2를 출력합니다).

6 | 6을 2로 나눈 몫인 3을 대상으로 다시 생각합니다.

7 | 3은 2로 나누어지지 않습니다.

8 | 이번에는 3으로 나눕니다.

9 | 3은 3으로 나누어지므로 3은 소인수입니다(3을 출력합니다).

10 | 3을 3으로 나누면 1이 되는데 제수(나누는 수)가 피제수(나뉘는 수)보다 크므로 계산을 멈춥니다.

 

지금부터 이 단계를 파이썬 프로그램으로 만들어 보겠습니다.