C언어의 기초 문법

유클리드 호제법

최대공약수를 구하는 쉬운 방법

※이건 수학과 관련된 프로그래밍입니다. 유클리드 호제법이 이해가 안 되신다면 넘어가셔도 좋습니다※

 유클리드 호제법, 들어보셨나요? 유클리드 호제법은 두 수의 최대공약수를 소인수분해 없이 구할 수 있는 방법입니다. 이해가 안 되실 수 있어요;;; 유클리드 호제법은 다음과 같이 정의할 수 있습니다.

  1.  두 수 중에서 큰 수를 a, 작은 수를 b라고 하고 a를 b로 나눈다.
  2. a가 b로 나누어떨어지면 두 수의 최대공약수는 b이다.
  3. a가 b로 나누어떨어지지 않으면 a를 b로 나눈 나머지와 b에 대하여 1번부터 다시 반복한다.

이렇게 계속 반복하면 최대공약수가 나오겠죠? 최대공약수가 나오면 최소공배수는 두 수의 곱을 최대공약수로 나누어 구할 수 있습니다. 이 유클리드 호제법을 한 번 반복문으로 짜볼 겁니다. 한 번 잠시 종이에 써보세요. 어려울 거에요. 프로그램의 결과와 소스 코드는 이렇게 됩니다.


입력: 4, 6 => 두 수를 입력합니다.

출력: 2 12 => 최대공약수와 최소공배수를 출력합니다. 만약 두 수 중 하나가 0이라면 프로그램을 종료합니다. 종료되기 전까지는 프로그램이 계속 반복됩니다.

...(a, b에 0이 입력될 때까지 반복)...


int a, b, c, d, e, gcd, lcm;
while (1)
{
    scanf("%d %d", &a, &b);
    if(a == 0 || b == 0)
    {
        printf("END");
        return 0;
    }
    if(a > b)
    {
        c = a;
        d = b;
    }
    else
    {
        c = b;
        d = a;
    }
    while (1)
    {
        e = c % d;
        if(e == 0)
        {
            gcd = d;
            lcm = a * b / gcd;
            printf("%d %d\n", gcd, lcm);
            break;
        }
        c = d;
        d = e;
    }
}
return 0;

와 어렵죠? 해석 들어갈게요

a, b를 두 수로 둡니다. c,d는 일단 두고 e를 a와 b를 나눌 나머지 변수로 둡니다. gcd와 lcm은 최대공약수와 최소공배수를 담는 변수입니다.

일단 a, b를 입력 받고, a, b 중 하나라도 0인지 확인합니다. 만약 참이라면 return 0;을 해서 프로그램을 종료하고, 아니면 다음으로 넘어갑니다(여기에는 굳이 else가 필요 없는게 if문이 참이라면 그냥 프로그램이 종료되어서 다음 코드로 넘어간다는 것은 if문이 거짓이라는 것이나 다름 없습니다)

이제 a, b를 큰 수, 작은 수로 정렬을 해야 합니다. 여기에서 c, d가 등장합니다. 일단 a가 큰지 b가 큰지 살펴보아야 합니다. 조건문으로 c에는 큰 수, d에는 작은 수를 놓습니다.

여기에서 또 무한 루프를 또 돌리는데요, 여기에서는 유클리드 호제법의 반복을 씁니다. c, d가 나누어 떨어질 때까지 나머지를 e로 저장해 계속 무한 루프를 돌리는 것입니다. 이렇게 하다 보면 결국 c, d가 나누어 떨어질 때가 있을 것입니다. 그 때 gcd에다가 d를 저장하고, lcm은 a * b / gcd를 하면 나오겠죠? 이 두 변수를 출력하고 반복문을 탈출합니다. 그러면 반복문이 바깥에 있는 반복문으로 돌아가서 처음부터 다시 시작하겠죠? a, b가 0이 되지만 않는다면요^^


와우 엄청 기네요. 이 유클리드 호제법은 재귀함수 때 다시 나올 거니까 그 때 다시 기다려주세요! 그때는 훨씬 더 쉬워질 거에요.

댓글

댓글 본문
  1. Joel
    네 감사합니다 ㅎㅎ
    대화보기
    • PARU
      코드를 주신 대로 복붙 했는데 자꾸 실행이 안 끝나서 계속 왜 이러지 왜 이러지 하다가 return 0; 위치 바꿔주니까 끝났어요.. 저걸 잊고 있었네요 ㅋㅋ 덕분에 최대 공약수 최소 공배수 구하는 식도 알고 갑니다!
    • joel
      이 부분은 질문이 많을 것이라고 예상이 되는데요;;; 질문할 것이 있다면 마음껏 질문해주세요! 제가 답해드리겠습니다!
    버전 관리
    Joel
    현재 버전
    선택 버전
    graphittie 자세히 보기