最大公約数の計算方法
JavaScriptで最大公約数と分数の約分の計算が必要な処理があったのだが最大公約数の計算方法をど忘れしていたため、備忘録のため記事に記載した。
ついでに約分計算機ツールも作成。
最大公約数をWikipediaで調べたら…
「最大公約数とは、少なくとも一つが0ではない複数の整数の公約数のうち最大の数を指す。」
…と書かれていた。
ちなみに公約数を調べると
公約数とは、2つ以上の自然数について、そのいずれの約数にもなることができる整数のことである。
…と書かれている。
つまりプログラマ向けに要約すると特定の整数nを整数mで割って余りが0であれば約数ということになる。
n % m === 0
例えば6の場合は以下のようになる。
const n = 6
const y = n => {
for (let i = 1; i <= n; i++) {
n % i === 0 ? console.log(`${i}は約数`) : ''
}
}
y(n)
// 1は約数
// 2は約数
// 3は約数
// 6は約数
最大公約数は複数の約数の最大値なので、例えば24と33なら前述の計算式で両方の約数を算出してMath.maxで最大値を取得すればどちらでも割れる最大の整数は3であることがわかる。
const yakubunMax = (a, b) => {
const arr = []
for (let i = 2; i <= a; i++) {
if (a % i === 0) arr.push(i)
}
for (let i = 2; i <= b; i++) {
if (b % i === 0) arr.push(i)
}
const filterArr = arr.filter(function (n, i, self) {
return self.indexOf(n) !== self.lastIndexOf(n);
})
return Math.max(...filterArr)
}
console.log(yakubunMax(24, 33)) // 3
