[10년 1회] 유클리드 호제법

입력 받은 두 수 A, B에 대한 최대공약수와 최소공배수를 유클리드 호제법으로 처리하려고 한다. 제시된 <그림>의 괄호 안 내용 (1)~(5)에 가장 적합한 항목을 <답항 보기>에서 선택하여 답안지의 해당 번호 (1) ~ (5)에 각각 마크하시오.

 

<처리조건>

- <그림> 의 순서도에 제시되어 있는 미완성 알고리즘을 분석하여, 가장 적합한 로직으로 구현될 수 있도록 답안을 선택하시오.

 

- 입력 받는 두수 A, B는 0이 아닌 서로 다른 양의 정수로 가정한다.

 

- MOD()는 괄호 안의 연산 수행하며 나머지를 구하는 함수이다. 예를 들어 MOD(5/3)의 값은 2이며, MOD(20/5)의 값은 0이다.

 

- 기호 “/” 는 나누기 연산 “*”는 곱셈 연산을 나타낸다.

 

 

최대공약수?

12의 약수 = 1, 2, 3, 4, 6, 12

18의 약수 = 1, 2, 3, 6, 9, 18

 

공약수: 공통된 약수를 보통 공약수라고 부른다.

12, 18의 공약수 : 1, 2, 3, 6

 

공약수 중에서 가장 큰 수가 최대공약수이다.

여기서는 6이다.

 

최소공배수?

2의 배수 = 2, 4, 6, 8, 10, 12, 14, 16, 18…

3의 배수 = 3, 6, 9, 12, 15, 18, 21, 24, 27…

 

공배수 = 6, 12, 18…

 

공배수 중에서 가장 작은 수가 최소 공배수이다.

 

유클리드 호제법?

큰수 / 작은수 -> 나머지

나머지가 0 이면 최대공약수 = 작은수, 최소공배수= 두수 곱/최대공약수

나머지가 0 이 아니면 큰수 = 작은 수, 작은 수 = 나머지