[2609번] 최대공약수와 최소공배수

최대공약수와 최소공배수 구하는 법을 까먹었다.

초등학교부터 다시 다녀야할 것 같다.

---

 

📌최대공약수와 최소공배수 구하는 방법

 

1. 소인수분해

 

• 두 수를 소인수분해를 한다. 두 수의 공통된 소인수를 모두 곱하면 최대공약수, 두 수의 모든 소인수를 곱하면 최소공배수가 된다.

 

2. 유클리드 호제법

 

• A와 B의 최대공약수를 구하기 위해서 A를 B로 나눈 나머지 R1을 구한다.
• B를 R1으로 나눈 나머지 R2를 구한다.
• R1을 R2로 나눈 나머지 R3를 구한다
• 이 과정을 계속 반복하여, 어느 한 쪽이 나누어떨어질 때까지 반복한다. 이 직전 얻은 나머지가 최대공약수.

예시로 1254와 582의 최대공약수를 구해보자.

 

• 1254=582×2+901254=582×2+90
• 582=90×6+42582=90×6+42
• 90=42×2+690=42×2+6
• 42=6×742=6×7

 

4단계에서 나누어떨어졌으며, 이 직전인 3단계의 나머지는 6이다. 따라서 1254와 582의 최대공약수는 6.

 

 

참고 :

https://dimenchoi.tistory.com/46

정수론 (1) - 최대공약수, 최소공배수, 유클리드 호제법

 

---

 

📌코드

#include <stdio.h>

int GCD(int D, int B);
int LCM(int a, int b, int gcd);

int main()
{
    int a, b, gcd;
    scanf("%d %d", &a, &b);

    //최대공약수
    gcd = GCD(a, b);
    printf("%d\n", gcd);

    //최소공배수
    printf("%d", LCM(a, b, gcd));
    return 0;
}

int GCD(int D, int B)
{
    int R;
    R = D % B; //D = B * (D/B) + R;
    if(R!=0) GCD(B, R);
    else return B;
}

int LCM(int a, int b, int gcd)
{
    return a * b / gcd;
}