[etc] 최대공약수,최소공배수구하기 - 유클리드 호제법

in Dev on Dev Note


최대공약수,최소공배수

문제 설명

고민

  • 최대공약수는 두 자연수의 공통된 약수 중에 가장 큰 수
  • 최소공배수는 두 자연수의 공통된 배수 중에 가장 작은 수 = 두 자연수의곱/최대공약수
  • 2개의 자연수를 받아 최대공약수를 받기 위해 2부터 두 자연수 중 작은 자연수까지 모두 나누어보면서 가장 큰 공약수를 구할 수 있다. -> O(N)
  • 유클리드 호제법 -> O(logN)

유클리드 호제법

유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

내 풀이


function solution(num1, num2) {
    
    var val = gcd(num1, num2);
    
    return [ val , num1 * num2 / val ];
}
    
function gcd(num1 , num2){
    if(num2 == 0){
         return num1;
    }else{
        return gcd(num2, num1 % num2);
    } 
}

M개의 최소 공배수

문제 설명

고민

N개의 최소 공배수를 하려면 1번째 2번째의 최소 공배수를 3번째 값과 또 최소 공배수를 구하고 그걸 또 4번째꺼와 구하고….

내풀이


function solution(a) {

    var val=1;
    var num1;
    var num2;
    for( var i=0; i<a.length ; i++){
        num1 = val; // pre 최소공배수
        num2 = a[i] // 다음값
        
        val = (num1*num2)/gcd(num1, num2);
        //  (num1*num2)/gcd(num1, num2)  -> 최소공배수
        //  gcd(num1, num2)  -> 최대공약수
    };
    return val;
}
    
function gcd(num1 , num2){
    if(num2 == 0){
         return num1;
    }else{
        return gcd(num2, num1 % num2);
    } 
}



© 2017. by isme2n