최소공배수, 최대공약수 - 유클리드 호제법

최대공약수 : gcd(a,b)

최소공배수 : lcm(a,b) = a*b/gcd(a,b)

최대공약수가 1인, 둘 이상의 양의 정수들은 서로소(relatively prime)

a = Gx, b = Gy (단, x, y는 정수)

일때... G 는 최대공약수

최소공배수는 a*b/G 임

---------------------- gcd(a,b) 구하기 설명

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42

1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 21

42는 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

    78696 ＝ 19332×4 ＋ 1368

    19332 ＝ 1368×14 ＋ 180

     1368 ＝ 180×7 ＋ 108 

      180 ＝ 108×1 + 72     

      108 ＝ 72×1 ＋ 36 

       72 ＝ 36×2

따라서, 최대공약수는 36이다.

----------------------------------------

예제

#include<stdio.h>

 

 

 

int max(int a, int b){

 

    if(a > b)

 

        return a;

 

    else

 

        return b;

 

}

 

int min(int a, int b) {

 

    if (a > b)

 

        return b;

 

    else

 

        return a;

 

}

 

  

/** 유클리드 알고리즘을 통해 최대 공약수와 최소 공배수를 구함. **/

 

int euclid(int a, int b) {

 

    if (b == 0)

 

        return a;

 

    return euclid(b, a % b);

 

}

 

 

 

/* 최대 공약수 */

 

int gcd(int a, int b) {

 

    return euclid(max(a, b), min(a, b));

 

}

 

 

 

/* 최소 공배수 */

 

int lcm(int a, int b) {

 

    return (a * b) / gcd(a, b);

 

}

 

 

 

/* 1~n까지의 최소 공배수 */

 

int getNumsLcm(int n) {

 

    int temp = 2;

 

    int i;

 

    for (i = 3; i < n; i++)

 

        temp = lcm(temp, i);

 

    return temp;

 

}

 

 

 

int main() {

 

 

    printf("%d", getNumsLcm(20));

 

    return 0;

 }

--------------------------

추가 : 

여러개의 숫자에서 구하기

http://selfc.tistory.com/3