[정보처리기사][알고리즘][수학] 최대공약수, 최소공배수

Q. 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 계산하여 출력하는 순서도를 작성하시오.

1. 최대공약수와 최소공배수를 구할 두수를 입력받는다.

2. A와 B의 대소를 비교하여 큰 수와 작은 수를 결정한다. 정황상 BIG에는 큰수가, SMALL에는 작은수가 저장된다.는 것을 생각한다.

1) A가 크거나 같은때, A가 큰수이므로 BIG에 A를 치환한다.

A. B가 작은 수이므로 SMALL에 B를 치환한다.

2) B가 큰수 이므로 BIG에 B를 치환한다.

A. A가 작은 수이므로 SMALL에 A를 치환한다.

3. 큰수를 작은 수로 나눈 나머지를 구하기 위해 큰 수를 작은수로 나누어 몫을 MOK에 저장한다.

4. 나머지를 구한다.

5. 최대공약수인지를 판별한다. 큰 수를 작은 수로 나누되 나머지가 0이면 그때의 작은수가 최대공약수라는 것을 생각한다.

1) No일 경우, 다음 계산을 위해 큰 수에 작은 수를 치환한다.

A, 다음 계산을 위해 작은 수에 나머지를 치환한다.

2) Yes일 경우, 작은 수가 최대공약수이므로 GCM에 SMALL을 치환한다.

A. 최소공배수는 원래의 두수를 곱한 후 최대공약수로 나눈 값이므로 최소공배수를 구하여 LCM에 저장한다.

6. GCM과 LCM을 출력한 후 종료한다.