최대공약수와 최소공배수 구하기

 

#include <stdio.h>

int main() {
    int a, b, high, low, m, n, gcm, lcm;
    
    // 두 수를 입력받음
    printf("두 수를 입력하시오: ");
    scanf("%d %d", &a, &b);
    
    // 더 큰 수와 작은 수를 구분
    if (a >= b) {
        high = a;
        low = b;
    } else {
        high = b;
        low = a;
    }

    // 유클리드 호제법을 이용하여 최대공약수 구하기
    while (1) {
        m = high / low; // 몫 구하기 
        n = high - (m * low); //나머지 구하기 
        if (n == 0) { // 나머지가 0이면 제수가 최대공약수
            gcm = low; 
            break; 
        }
        high = low; // 피제수를 제수로 넣기 
        low = n; // 나머지를 피제수로 넣기 
    }

    // 최소공배수 구하기
    lcm = (a * b) / gcm;

    // 결과 출력
    printf("최대공약수: %d\n", gcm);
    printf("최소공배수: %d\n", lcm);

    return 0;
}

두 수를 입력하시오: 
7
8
최대공약수: 1
최소공배수: 56

 

#include <stdio.h>

int main() {
    int a, b, high, low, m, n, gcm, lcm;
    
    // 두 수를 입력받음
    printf("두 수를 입력하시오: \n");
    scanf("%d %d", &a, &b);
    
    // 더 큰 수와 작은 수를 구분
    if (a >= b) {
        high = a;
        low = b;
    } else {
        high = b;
        low = a;
    }

    // 유클리드 호제법을 이용하여 최대공약수 구하기
    while (1) {
        
        n = high % low; // 이 부분만 바꿔서 
        if (n == 0) {
            gcm = low;
            break;
        }
        high = low;
        low = n;
    }

    // 최소공배수 구하기
    lcm = (a * b) / gcm;

    // 결과 출력
    printf("최대공약수: %d\n", gcm);
    printf("최소공배수: %d\n", lcm);

    return 0;
}

두 수를 입력하시오: 
25
10
최대공약수: 5
최소공배수: 50

 

 

---

 

 

유클리드 호제법은 두 개의 자연수의 최대공약수를 구하는 알고리즘 중 하나입니다. 이 방법은 간단하면서도 효율적으로 최대공약수를 계산할 수 있습니다. 다음은 유클리드 호제법의 간단한 설명입니다.

1. **두 수의 크기 비교**: 먼저 두 수 중 큰 수와 작은 수를 구분합니다.

2. **큰 수를 작은 수로 나누기**: 큰 수를 작은 수로 나눈 나머지를 구합니다.

3. **나머지가 0인지 확인**: 만약 나머지가 0이면, 작은 수가 두 수의 최대공약수입니다. 그렇지 않다면, 이전의 작은 수를 새로운 큰 수로 하고, 이전의 나머지를 새로운 작은 수로 하여 나눗셈을 반복합니다.

4. **나머지가 0이 될 때까지 반복**: 나머지가 0이 될 때까지 위 과정을 반복합니다. 이 때, 나누는 수가 나머지가 되고, 이전의 나머지가 새로운 나누는 수가 됩니다. 이 과정을 반복하면 결국 나머지가 0이 되고, 그 때의 나누는 수가 두 수의 최대공약수가 됩니다.

이해를 돕기 위해 간단한 예제를 들어보겠습니다.

예를 들어, 24와 18의 최대공약수를 구하려고 합니다.

- 먼저 24와 18 중에서 큰 수는 24이고 작은 수는 18입니다.
- 24를 18로 나눈 나머지는 6입니다.
- 이제 18을 새로운 큰 수로, 6을 새로운 작은 수로 설정하여 다시 나눕니다.
- 18을 6으로 나눈 나머지는 0이므로, 최대공약수는 6이 됩니다.

즉, 24와 18의 최대공약수는 6입니다.

이와 같이 유클리드 호제법은 나머지가 0이 될 때까지 두 수를 반복해서 나누는 과정을 통해 최대공약수를 구합니다. 이 알고리즘은 재귀적으로 구현할 수도 있고, 반복문을 사용하여 구현할 수도 있습니다.

 

출처: chatgpt