[ 알고리즘 ] 유클리드 호제법을 사용한 최대공약수, 최소공배수

 

최대공약수

a를 b로 나누었을때 ( a가 b보다 커야한다 ) b를 새로운 a로, a를 b로 나눈 나머지를 새로운 b로 해서 나머지가 0 일 때 까지 반복한다

function gcd(a,b){ // a is greater than b
	let R ;
    while( (a % b) > 0 ){
    	R = a % b 
        a = b 
        b = R  
    }
    return b
}

 

재귀함수를 사용해서 최대공약수 구하기

function gcd(a,b){
	if(b  == 0 ){
    	return a
    }
    gcd(b, (a % b ));
}

최소공배수

두 수 a 와 b 를 곱하고 최대공약수로 나눈다.

function lcm(a,b){
	a * b / gcd(a,b)
}