최대공약수 (The Greatest Common Denominator(GCD)), 최소공배수(The Least(Lowest) Common Multiple(LCM))

*최대공약수 (The Greatest Common Denominator(GCD)), 최소공배수(The Least(Lowest) Common Multiple(LCM))

 

 

# Algorithm 1 : 간단한 방법(Simple Way)을 이용한 최대공약수(GCD) 구하기

 

int min(int a, int b)
{
    if (a > b) return b;
    else if (a < b) return a;
    else return a;
}

// 간단한 최대공약수 알고리즘 (A simple algorithm of the greatest common denominator(GCD))                                  
 
int gcd(int m, int n)
{
    int g;
    for (g = min(m,n); g>=1; g--)
        if ((m % g == 0) && (n % g == 0))
            return g;
}

 

# Algorithm 2 : 유클리드 호제법(Euclidean Algorithm)을 이용한 최대공약수(GCD) 구하기

 

// Euclidean Algorithm 
 
#include <stdio.h>
 
int gcd(int m, int n) // It is assumed that m <= n.                                                                           
{
    if (m == 0) return n;
    else return gcd(n % m, m);
}
 
void main(void)
{
    int m, n; // positive integers
    int result; // gcd of m and n
    scanf_s("%d", &m);
    scanf_s("%d", &n);
    if (m <= n) result = gcd(m, n);
    else result = gcd(n, m);
    printf("%d\n", result);
}

 

+ Algorithm : 최대공약수를 이용한 최소공배수(LCM) 구하기

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