paizaラーニング レベルアップ問題集 paizaの森練習問題コンテスト過去問題7 JavaScript 最も大きな最大公約数

最も大きな最大公約数 (paizaランク C 相当)

解答例

1 から n までの範囲にある全ての異なる整数の組、例えば(a, b)をforループで回しながら、
aとbの最大公約数を求め、それが最も大きな最大公約数か判定する。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n] = lines[0].split(" ").map(Number);

//ユークリッドの互除法の関数定義
const gcd = (x, y) => {
  let r;
  while ((r = x % y) !== 0) {
    x = y;
    y = r;
  }
  return y;
};

//1 から n までの範囲にある全ての異なる整数の組(a,b)のうち
//最も大きな最大公約数maxを求める
let max = 1;
for (let a = 1; a < n; a++) {
  for (let b = a + 1; b <= n; b++) {
    max = Math.max(gcd(a, b), max);//関数を実行して、最も大きいか判定
  }
}
console.log(max);