LoginSignup
8
8

More than 5 years have passed since last update.

js 複数の数字の最小公倍数を求める(ユークリッドの互除法使用)

Last updated at Posted at 2017-01-20

お題

引数で与えらえた二つの数字の範囲の数の最小公倍数をもとめる。
例 引数[5,1]の場合、1,2,3,4,5の最小公倍数60を求める
・n>0
・二つの数字の並びは昇順とは限らない

最大公約数 greatest common divisor
2つ以上の整数において,それらに共通する約数を公約数といい,公約数のうち最大のものが最大公約数
最小公倍数 least common multiple
2つ以上の整数において,それらに共通する倍数を公倍数といい,正の公倍数のうち最小のものが最小公倍数

function smallestCommons(arr) {
    //write your code.
}
smallestCommons([5,1]); //60

出力結果 例

([1,7])//420
([1, 13])// 360360
([23, 18])// 6056820

つかったもの

Math.max()
Math.min()
push()
reduce()
for文
if文
ユークリッドの互除法
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

考え方

・引数から範囲の数字を降順に配列にいれる。(最初の二つの数の最小公倍数が共通の公倍数である可能性が高くなる)
Math.max(),Math.min()で最小と最大の数を判定し、用意した配列にfor文で範囲の数をpush()する。

・最小公倍数(lcm)は二つの数を掛けて、最大公約数(gcd)で割ると求めることができる。
例 5と4の場合、5*4/1=20 20がlcm 1はgdc

連続する数字の最小公倍数を求める場合は最初の二つの数のlcmを求め、lcmと次の数のlcmをもとめてlcmを更新していく。最後に返ってくる数が全体のlcm。
二つの数の比較はreduce()またはfor文などで実行できる。

例 [5,1]の場合 →[5,4,3,2,1]
5*4/1 =20
20*3/1 =60
60*2/2 =60
60*1 =60  全体のlcmは60

・gdcはユークリッドの互除法を使って求める
→剰余が 0 になった時の除数が a と b との最大公約数

例 5と4のgdc
5÷4 = 1・・・1
4÷1 = 1・・・0
1がgdc

コード

function smallestCommons(arr) {
    var range = [];
    for (var i = Math.max(arr[0], arr[1]); i >= Math.min(arr[0], arr[1]); i--) {
    range.push(i);
    }

    return range.reduce(function(previousValue, currentValue) {
    var gcdPrevCurr = gcd(previousValue, currentValue);
    return (previousValue * currentValue) / gcdPrevCurr;
    });

    function gcd(x, y) {    // ユークリッドの互除法使用
    if (y === 0)
        return x;
    else
        return gcd(y, x%y);
    }
}
smallestCommons([5,1]);//60

他にもコードが浮かんだ方、コメントお待ちしております。

8
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8
8