[정보처리기사][알고리즘][수학] 소인수 분해하기

Q. 정수를 입력 받아 소인수를 구해 출력하는 순서도를 작성하시오.

1. 소인수를 저장할 배열 A를 선언한다.

2. 소인수로 분해할 숫자를 입력 받는다.

 

3. 소인수를 저장할 배열의 위치 C를 0으로 치기화한다.

 

4. 소인수를 구할 때 사용되는 제수가 저장될 변수 D를 초기화한다. 소인수를 구할때도 피제수를 2부터 나눠준다는 것을 생각한다.

 

5. 입력받은 값 B의 제곱근을 구해 정수로 변환한 후 E에 저장한다.

 

6. 제수가 피제수의 제곱근보다 크면 그때는 피제수 자체가 입력받은 수의 소인수이므로 YES로 가고, 아니면 NO로 간다.

 

YES 경우

A. B 자체가 소인수이므로 이에 알맞은 처리를 한다.

 

NO 경우

A. B를 D로 나눈 몫을 MOK에 저장한다.

 

B. B를 D로 나눈 나머기를 구하여 NMG에 저장한다.

 

C. 소인수이니지를 판별한다. 처음으로 나머지가 0이 되게 하는 수가 그 수의 소인수라는 것을 생각한다.

 

YES일 경우

ㄱ. 7번으로 간다.

 

NO일 경우

ㄱ. D를 2부터 B의 제곱근까지 증가 시키기 위해 1을 더한다.

 

ㄴ. 6번으로 간다.

 

7. 배열의 위치를 지정하는 C를 1부터 차례로 증가시키기 위해 1을 더한다.

 

8. A(C)에 소인수 D를 저장한다.

 

9. B와 D가 같으면 소인수 분해 과정을 모두 마친것이므로 YES로 가고, 아니면 NO로 간다.

 

YES일 경우

1) 10번으로 간다.

 

NO일 경우

1) 소인수를 구했으면 그때의 몫에 대해 다시 소인수를 구하기 위한 처리를 한다.

 

2) 5번으로 간다.

 

10. 배열에 저장된 소인수를 출력하고 끝낸다.

해당 글은 제가 만든 어플을 기준으로 작성하였습니다.

더 많은 정보는 알고리즘 어플을 이용해주세요.