유클리드 호제법이란?

유클리드 호제법2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.라는 성질을 활용하여 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 방법이다.

최대 공약수 구하기

//  JavaScript
//  유클리드 호제법
function findGcd(a, b) {
	const remainder = a % b
    if (remainder === 0)
        return b
    return findGcd(b, remainder);
}

// 일반적인 방법
function findGcd(a, b) {
    let gcd = 1;
    for (let i = 2; i <= Math.min(a, b); i++)
    {
        if (a % i === 0 && b % i === 0)
            gcd = i;
    }
    return (gcd);
}

최소 공배수 구하기

// JavaScript
// 유클리드 호제법
let lcm = (a * b) / findGcd(a, b);

// 일반적인 방법
function findLcm(a, b) {
    let lcm = 1
    while (42)
    {
        if (lcm % a === 0 && lcm % b === 0)
            break ;
        lcm++;
    }
    return lcm;
}

예시 문제

function findGcd(a, b) {
    const remainder = a % b
    if (remainder === 0)
        return b
    return findGcd(b, remainder);
}

function solution(a, b) {
    let answer = [];
    let gcd = findGcd(a, b);
    let lcm = (a * b) / gcd;
    answer.push(gcd);
    answer.push(lcm);
    return answer;
}