paiza 問題集最小公倍数 js

素数メニュー【素因数分解・約数の個数・最大公約数・最小公倍数】

Task

整数 N を素因数分解してね。

【素因数分解】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   let n = N;
   const prime_factor = [];  // 素因数分解した値を保存するための配列
   for (let i = 2; i <= n; i++) {
      while (n % i === 0) {  // n が i で割り切れる間…
         prime_factor.push(i);  // 素因数分解した値として保存
         n /= i;  // n を n / i で上書き
      }
   }
   prime_factor.forEach(value => {
      console.log(value);
   });
});

n が i で割り切れる間 prime_factor に i を素因数分解した値として保存して n を n / i で上書きしています。

top

問題【STEP: 2】約数の個数

Task

整数 N の約数が何個あるか求めてね。

【約数の個数】コード

reader.on('close', () => {
   let n = Number(lines[0]);
   const prime_factor = new Map();  // key=>素数, value=>累乗
   for (let i = 2; i <= n; i++) {
      while (n % i === 0) {  // n が i で割り切て…
         if (prime_factor.has(i)) {  // i (key)が既に含まれている場合
            const p = prime_factor.get(i);  // i の値 を p に代入
            prime_factor.set(i, p + 1);  // i の値を p + 1 で上書き
         } else {  // i(key)が含まれていない場合
            prime_factor.set(i, 1);  // key=>i, value=>1 を追加
         }
         n /= i;  // n を n / i で上書き
      }
   }
   let power = 1;  // 約数の数を初期化
   prime_factor.forEach(value => {
   power *= value + 1;  // power を power × (value(素数の累乗)) + 1 で上書き
   });  
   console.log(power);
});

求めたい値はN を素因数分解したときに現れる全ての{素数の累乗 + 1} の積なので素数の累乗を求めるために keyが素数, valueが累乗の Map() を生成しました。

top

問題【STEP: 3】最大公約数

Task

N 個の整数 A_1〜 A_N の最大公約数を求めてね。

【最大公約数】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const prime_factor = new Map();  // key=>素数, value=>[累乗,…]
   for (let i = 1; i <= N; i++) {
      let a = Number(lines[i]);  // 入力を a で受取り
      for (let j = 2; j <= a; j++) {
         while (a % j === 0) {  // a が j で割り切れる間…
            const p = prime_factor.get(j);  // p は キー が j の値(配列)
            if (p && p.length === i) {  // p の要素数が i なら…
               p[i - 1]++;  // p[i]の値を 1 加算
            } else if (p && p.length === i - 1) {  // j の要素数が i なら…
               p.push(1);  // p[i - 1]の値を 1 加算
            } else if (i === 1) {  // i が 1 なら
               prime_factor.set(j, [1]);  // prime_factor に (j, [1]) を追加
            }
            a /= j;  // a を a / i で上書き           
         }
      }
   }
   let gcd = 1;  // 最大公約数を初期化
   prime_factor.forEach((value, key) => {
      if (value.length === N) {  // 値(配列) の要素数が N の場合のみ
         gcd *= (key ** Math.min(...value));
      }
   });
   console.log(gcd);
});

求めたい値は「全ての整数に共通する素因数の{最小の指数}乗」の積…。
カウント変数 j の for文に含まれる if文の条件分岐が複雑になっています。 j の値(配列)の要素数が i 未満の時は全ての整数に共通するという条件が当てはまらないので値に変化はありません。

top

問題【FINAL】最小公倍数

Task

A_1 〜 A_N の最小公倍数を求めてね。

【最小公倍数】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const S = new Set();  // 重複を削除するために 入力値をSet()に保存
   for (let i = 1; i <= N; i++) {
      S.add(Number(lines[i]));
   }
   const A = [...S];  // 配列 A に S を展開 した値を保存
   const M = A.length;  // 配列 A の要素数を M に保存
   const prime_factor = new Map();  // key=>素数, value=>[累乗,…]
   for (let i = 0; i < M; i++) {
      let a = A[i];  // A の各値を順次 a に保存して…
      for (let j = 2; j <= a; j++) {
         if (a % j === 0) {  // a が j で割り切れて…
            if (prime_factor.has(j)===false) {  // j (key)が含まれていない場合
               prime_factor.set(j, new Array(M).fill(0));  // j(素数), [0,0,…]を追加
            } 
            prime_factor.get(j)[i]++;  // j の値の i 番目の要素に 1 加算
            a /= j;
            j--;
         }
      }
   }
   let lcm = 1;  // Aの各値の素因数の{最大の指数}乗を保存
   prime_factor.forEach((value, key) => {
      lcm *= (key ** Math.max(...value));
   });
   console.log(lcm);
});

「全ての整数のうちいずれかの整数の素因数の{最大の指数}乗」。

top