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

최대공약수를 구할때는 "유클리드 호제법"을 사용하는것이 편하다.

유클리드 호제법이란? 단순하게 설명해서

1. 큰 수에서 작은 수를 나눈 나머지를 구한다.(큰 수 작은 수의 구분은 크게 의미가 없고 단지 먼저수와 나중수의 의미가 크다.)
2. 작은 수가 큰 수, 나머지가 작은 수의 역활을 하여 1의 과정을 다시한다.
3. 2의 과정을 하다가 나머지가 0 이며 종료한다.
4. 마지막으로 나눈 값이 최대공약수 이다.

그럼 최소공배수는 어떻게 구하나?
최대공약수로 처음의 큰 수와 작은 수의 곱을 나누면 된다.

큰수 * 작은수 / 최대공약수

예)두수를 입력받아서 최대공약수와 최소공배수 구하기

소스)

int EU(int x, int y)
{
    int n;
    while (1){
         n = x % y;
         if (n == 0) return y;
         x = y;
         y = n;
    }
}

int main()
{
    int gcm, lcm, su1, su2;
    scanf("%d %d",&su1, &su2);

    gcm = EU(su1, su2);
    lcm = su1 * su2 / gcm;

    printf("최대공약수 = %d\n", gcm);
    printf("최소공배수 = %d\n", lcm);

 return 0;
}

그럼 3개 이상의 수에서는 어떻게 구할까?

1. 처음 하나의 숫자를 최대공약수와 최소공배수로 정의한다. (숫자가 하나 일 때는 그 수가 최대공약수, 최소공배수이기 때문이다.)
2. 지금까지 구해놓은 최대공약수와 새로운 수로 최대공약수를 구한다.
3. 또 지금까지 구해놓은 최소 공배수와 새로운 수로 최소공배수를 구한다. 주의 - 최소공배수 * 새로운 수를 나눌때는 지금 곱하는 두 수의 최대공약수로 나누어야한다.
4. 2, 3 과정을 모든 숫자가 끝날때까지 반복한다.

예) 5개의 숫자를 입력 받아 최대공약수와 최소공배구수 구하기

소스)

int EU(int x, int y)
{
    int n;
    while (1){
        n = x % y;
        if (n == 0) return y;
        x = y;
        y = n;
    }
}

int main()
{
    int gcm, lcm, su, i;
    scanf("%d",&su);
    gcm = lcm = su;

    for(i=1; i<5; i++){
        scanf("%d",&su);
        gcm = EU(gcm, su);
        lcm = lcm * su / EU(lcm, su);
    }

    printf("최대공약수 = %d\n", gcm);
    printf("최소공배수 = %d\n", lcm);

    return 0;
}