Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

JavaScriptで素因数分解アプリを作る

More than 1 year has passed since last update.

こんなやつ

Image from Gyazo

動作デモ → https://jsfiddle.net/vw98komL/

自分流素因数分解のアルゴリズム

前提

そもそも素因数分解とは、「自然数を素数の掛け算の形にすること」です。

例: 120 → 2 * 2 * 2 * 3 * 5 → 2^3 * 3 * 5

単純に約数を並べる訳ではないので、一つの数字が複数回でてくる事もあります。

本題

前提を踏まえて考えると、まず対象の自然数(valueと置く)の約数を見つける必要があります。

①約数はループ処理を用いて2から順にvalueに対して%演算子で剰余が0のもの(divisorと置く)。
②次に指数は、こちらもループ処理を用いて、valuedivisorで剰余が0である間は除算し続け、その中でカウンターを増やしていき求める。

この流れで1つ目の素因数が見つかります。

以降はこれの繰り返しで、前の処理で除算されたvalueに対してまた①で約数を見つけて②でその指数を求めます。
そしてdivisorvalueと等しくなる(value / divisor === 1)までそれを繰り返せば素因数分解は完了です。

コード

HTML
<input id="prime-factorization" type="number">
<p>結果:<span id="result"></span></p>
JavaScript
const box = document.querySelector('#prime-factorization');
const result = document.querySelector('#result');

const checkDivisors = () => {
  let value = box.value;
  let exponent = 0;
  let divisors = [];

  for(let number = 2; number <= value; number++) {
    //前述の①の処理
    if(value % number === 0) {
      //前の約数の分のカウントをリセットする
      exponent = 0;
      //同様に②の処理
      while(value % number === 0) {
        //valueをnumberで除算していき、ループごとにカウントを一つ増やして累乗の指数を求める
        exponent++;
        value /= number;
      }
      //一つ目の約数と指数を配列にpush
      divisors.push({number, exponent});
    }
    //この流れを(value / number === 1)になるまで繰り返す
  }

  //連続して使用する時のために一度中身を空にする
  box.value = null;
  result.textContent = null;

  //上記のループ処理で求めた素因数が格納された配列を展開
  divisors.forEach((divisor, index) => {
    if(index === divisors.length - 1) {
      //最後はスペースと*が要らない
      result.textContent += `${divisor.number}^${divisor.exponent}`;
      return;
    }
    result.textContent += `${divisor.number}^${divisor.exponent}\n*\n`;
  })
}

box.addEventListener('keydown', e => {
  if(e.key === 'Enter') {
    checkDivisors();
  }
})

出来ました。(*゚▽゚ノノ゙☆パチパチパチ

Image from Gyazo

taku-hu
普段はReact・Vueあたりを書いてるフロントエンドエンジニア。 好きな言語はTypeScript。
https://taku-hu.web.app/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away