C 언어로 재귀 함수 없이 두 수의 최대공약수(GCD) 구하기

문제 정의

주어진 두 정수의 최대공약수(GCD, Greatest Common Divisor)를 재귀 함수를 사용하지 않고 구하는 것이 이번 문제의 목표입니다.

해결 방법

두 수의 최대공약수는 유클리드 호제법(Euclidean Algorithm)을 활용하면 효율적으로 구할 수 있습니다. 아래에서는 반복(비재귀) 방식으로 GCD를 계산하는 절차와 C 프로그램 예제를 소개합니다.

알고리즘

다음은 재귀 호출 없이 두 수의 최대공약수를 구하는 알고리즘입니다.

1단계 − 시작합니다.

2단계 − 두 개의 정수 a와 b를 입력받습니다.

3단계 − 함수를 호출합니다: G = GCD(a, b)

4단계 − 결과값 G를 출력합니다.

5단계 − 종료합니다.

6단계 − 호출된 함수 내부 처리: GCD(a, b)

a. 변수 i=1, j, 나머지(remainder)를 초기화한다.
b. 나머지 = i - (i / j * j)
c. 나머지가 0이면 j를 반환하고, 그렇지 않으면 다음 단계로 이동한다.
d. GCD(G, remainder)를 계산하여 메인 프로그램으로 결과를 반환한다.

플로우차트

아래는 위 알고리즘의 처리 흐름을 시각적으로 나타낸 플로우차트입니다.

C 프로그램 예제

다음은 재귀 함수를 사용하지 않고 두 수의 최대공약수를 구하는 C 프로그램입니다.

#include<stdio.h>
#include<conio.h>
#include<math.h>
int gcdnonR(int i,int j){
    int rem;
    rem=i-(i/j*j);
    if(rem==0)
       return j;
    else
       gcdnonR(j,rem);
}
void main(){
    int a,b;
    printf("enter the two numbers:");
    scanf("%d%d",&a,&b);
    printf("GCD of %d",gcdnonR(a,b));
    getch();
}

코드 설명

• gcdnonR 함수는 나눗셈의 나머지를 이용해 유클리드 호제법을 구현합니다.
• rem = i - (i/j*j) 연산은 i % j(모듈로 연산)와 동일한 결과를 냅니다.
• 나머지가 0이 되면 그때의 j 값이 곧 최대공약수입니다.

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

enter the two numbers:10 30
GCD of 10

입력한 두 수 10과 30의 최대공약수인 10이 정상적으로 출력되는 것을 확인할 수 있습니다.