テストエンコーディング|(JavaScript)プログラマー:最大公倍数と最大公倍数


に質問


2つの数を入力し、2つの数の最大公約数と最小公約数の関数を返し、解を完了します.アレイの先頭にある最大公約数、次に最小公約数を返します.例えば、2つの数3および12の最大承諾数は3であり、最小公倍数は12であるため、ソリューション(3、12)は[3、12]を返さなければならない.

制限

  • の2つの数字はいずれも100000を超える自然数である.
  • 🎹📢I/O例



    ほどく

    function solution(n, m) {
        let answer = [];
        
        // 유클리드 호제법을 이용해 최대공약수를 구한다.
        let r, a = m, b = n;    
        // 큰 수에서 작은 수로 나눈 나머지 값이 0이 될 때 까지 반복한다. 
        while(b > 0){
            r = a % b;
            a = b;
            b = r;
        }
        // 0이 되었을때 마지막으로 나눈 값 a는 최대공약수 이다.
        answer.push(a);
        
        // 최소공배수는 n과 m의 곱을 최대공약수 a로 나눈 것과 같다.
        answer.push(n * m / a);
        
        return answer;
    }
    過去に解いたことがあるので,忘れてから解く.まず,mが大数nで小数であると仮定する.最大公約数を求める標準的な方法は小数分解であるが,大数はあまりにも非効率であり,ユークリッドアーク除去アルゴリズムにより効率を向上させることができる.최소공배수 * 최대공약수 = n * mが設立されました.したがって,最小公倍数でも最大公倍数でも1つだけ要求し,残りは容易に得られる.従って,効率の観点から,ユークリッドアーク法は有利であり,まず最大公倍数を求め,次に最小公倍数を求める.최소공배수 = n * m / 최대공약수次に、一般に最大公約数と最小公約数を計算する方法を示す.

    上記の例の최대공약수: 2 * 2 * 3 = 12최소공배수: 2 * 2 * 3 * 3 * 5 = 180
    上記の例の최대공약수: 2 * 3 * 5 = 30최소공배수: 2 * 3 * 5 * 2 * 3 = 180

    参考資料とサイト(ありがとうございます)

  • https://programmers.co.kr/learn/courses/30/lessons/12940
  • http://textbook-miraen.cdn.x-cdn.com/ele_math/5st/E4.pdf
  • http://textbook-miraen.cdn.x-cdn.com/ele_math/5st/E5.pdf