유클리드 호제법

개요 :

유클리드 호제법이란 두 수의 최대공약수(GCD)를 구하는 하나의 알고리즘이다.
고대 그리스 수학자 유클리드가 제시한 알고리즘으로, 두 수의 나누어떨어지는 관계를 반복적으로 활용하여 가장 큰 공약수를 빠르게 구할 수 있다.

원리 :

두 수 a와 b에 대해, a가 b로 나누어떨어지지 않으면, 그 나머지를 구하고, 그 나머지와 b로 최대공약수를 구하는 방식입니다. 이 과정을 반복해서 나머지가 0이 될 때까지 진행하면, 그때의 b가 a와 b의 최대 공약수입니다.

사용 조건 :

1. 두 수 a와 b가 주어져야 한다.
2. a와 b가 정수여야 한다.
3. 두 수 중 적어도 하나는 0이 아니어야 한다. (48과 0의 최대 공약수는 48, 18과 0의 최대 공약수는 18)

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    int r;
    while (b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    cout << (a * b) / gcd(a, b) << endl;
}

 

문제 풀어보기 : BeakJoon