정보처리기능사 실기 기출문제 유형#3 - 소인수분해 알고리즘

You shook me all night long!

정보처리기능사 실기 기출문제 유형#3 - 소인수분해 알고리즘

1. 소인수분해?

- 어떤 수가 있다고 치자, 그 수는 그수를 구성하고있는 소수의 곱으로 표현될 수 있는데

이러한 특수한 수학적 표현법을 "소인수분해"라고 한다.

소인수분해 예 : 21을 소인수분해하면, 21 = 3 X 7 이 된다. 20을 소인수 분해하면 2 x 2 x 5 이다.

2. 소인수분해 알고리즘의 원리

- 일단 어떤수N를 입력받는다.

- N의 제곱근을 정수 타입으로 구한다.

- 이제, 2부터 시작해서 위에서 구한 제곱근까지 어떤수N를 차례로 나눠주면서 처음 나누어떨어지는 수가

등장하면 바로 그 수가 바로 N을 구성하는 소인수중 하나가 된다. Capisci?

- 그 다음부터는 N을 위에서 구한 소인수로 나눈뒤 N에 저장하고 자체가 소인수가 될때까지 위를 반복한다.

15를 예로들면

- 15 입력!

- 루트15 = 3.xxx

- 이제 2부터 3까지 차례로 15를 나눠서 나누어 떨어지는게 있나 확인. 당연히 "3"당첨.

- 15 / 3 = 5 나눠주고 다시 시작. 

- 루트5 = 2.xxx

- 이제부터 2부터 2까지 차례로 5를 나눠서 나누어 떨어지는게 있나 확인. 당연히 없음. 이런경우 "5" 당첨.

당첨자 : 3, 5

15 = 3 x 5 소인수분해 끝.