정수의 소인수 분해 1. - 코딩수업#16

다음에서 소인수 분해에 대한 정의를 살펴보니 다음과 같이 요약되어 있다.

어떤 수를 몇 개의 곱으로 나타낼 때, 곱해진 수를 인수라 한다. 또 인수 중 소수인 것을 소인수라 한다.
자연수를 소인수들만의 곱으로 나타낸 것을 소인수분해라 한다.

초등학교 고학년이나 중학교 1학년 때 쯤 배운 것 같은 이 내용을 코딩으로 풀어보자.

웹 화면에서 특정 정수를 입력하면 해당 인수와 그 인수의 지수를 보여주는 프로그램을 만들어 보는 것이다.

특정 숫자를 입력하는 부분이 앞서 개발환경이 변경된 것을 테스트해볼 수 있는 좋은 예제가 될 것 같아서 이 문제를 골랐다.

6=2X3

15=3X5

60=2²X3X5

이런 것들이 소인수 분해인 것이 기억나시는지?^^

소인수 분해를 하려면 일단 소수에 대하여 이해해야 한다.

소수는 자기 자신과 1을 제외하고는 어떤 수로도 나눠지지 않는 수이다. 

2, 3, 5, 7, 11, 13, 17, 19 ...... 와 같은 숫자이다.

그리고 소인수 분해는 특정 숫자를 소수만의 곱으로 나타내는 과정이다.

프로그램의 기본 개념을 살펴보자.

1. 소인수 분해를 원하는 숫자를 n이라고 하자.

2. 먼저 가장 작은 소수인 2를 가지고 n을 나누어 보자

3. 만일 나머지가 없을 경우 몫을 n이라 생각하고 2번의 작업을 반복한다. (반복 횟수를 기록한다.)

    나머지가 없을 경우 다음 단계로 넘어간다.

4. 3번의 작업에서 나누어지지 나머지가 발생한 남은 숫자를 n이라 생각하고 다음 소수에 해당하는 숫자로 n을 나누어 본다. 이 작업 역시 나머지가 없을 경우 자기 자신으로 밖에는 나누어지지 않는 숫자가 나올 때까지 이를 반복한다.

   예) 

    84의 경우 2로 나누면 42가 남고 

    다시 나누면 2로 나누면 21이 남고  

    2로는 더 이상 나누어지지 않으므로

     다음 소수인 3으로 나누어 

     7이 나오면 더 이상 자기 자신인 7 이외의 수로 나누어지지 않는다.

     84=2² X 3 X 7이라고 표시할 수 있다.

     이때 2, 3, 7은 인수이고, 그 곱의 숫자를 나타내는 2,1,1 은 지수가 된다.

     다시 한번 풀어쓰자면

     84=(2X2) X (3X1) X (7X1) 이 되는 것이다.

본 프로그램은 특정 정수를 입력 창에 입력하면, 해당 숫자의 소인수 분해를 통하여 인수와 지수를 구하여 그를 출력하는 프로그램이다.

우리는 2,3,5,7,11,13과 작은 숫자의 소수들은 이미 알고 있어 이를 이용하여 나눗셈을 했겠지만, 프로그램에서는 숫자를 하나씩 대입해 보는 과정을 반복해야 한다. 이러한 알고리즘을 아래와 같이 도식화해보자.

만일 최초의 개발환경에서 이를 검사한다면 아래의 그림과 같이 표현될 것이다.

각 소수와 해당 지수의 값을 출력하는 부분을 추가하였다.

위의 코드로도 소인수분해는 가능하다. 그러나 2와 3 이후의 소수를 가지고 계산하는 부분도 하나로 합칠 수 있고, 새로운 웹 환경에서의 개발을 통해서 변수 num을 코드에서가 아니라 웹 화면에서 변경하여 처리하는 부분을 표현할 수도 있을 것이다.

이 부분은 다음 강좌에서 마무리하도록 하자.