[알고리즘] C# 최대 공약수와 최소 공배수 구하기, 유클리드 호제법

최대공약수

최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 

// n >= m

int n = 10;
int m = 6;

int gcd = getgcd(n, m); // 2

int getgcd(int a, int b)
{
    if(a % b == 0)
    {
        return b;
    }
    else
    {
        return getgcd(b, a % b);
    }
}

 

최소공배수

최소공배수는 두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수를 뜻합니다.

// n >= m

int n = 10;
int m = 6;

int gcd = getgcd(n, m); // 2
int lcm = n * m / gcd; // 30

int getgcd(int a, int b)
{
    if(a % b == 0)
    {
        return b;
    }
    else
    {
        return getgcd(b, a % b);
    }
}

 

참조

• 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)