試し割り法で素因数分解する
N予備校 「大規模Webアプリ Scala基礎 > Scala基礎コース > 03.Scala で解く素因数分解」にて、「試し割り法」という方法で素因数分解をする方法が紹介されていたので、教材のScalaではなくJavaScriptで書いてみました。
'use strict'; const num = 1536; const maxWarukazu = Math.sqrt(num); const waruKazuInit = 2; /* * 試し割法で素因数分解する * @param {int} motomeruKazu 素因数分解される数。 * @param {int} waruKazu motomeruKazuを割る素数 * @param {Array} result 結果を保存する配列 * @return {Array} 素因数分解の結果が保存された result を返す */ function factorial(motomeruKazu, waruKazu, result){ if (warukazu > maxWarukazu){ if(motomeruKazu !== 1) result.push(motomeruKazu); return; } if(motomeruKazu % waruKazu === 0){ result.push(waruKazu); motomeruKazu = motomeruKazu / waruKazu; factorial(motomeruKazu, waruKazu, result); } else { waruKazu += 1; factorial(motomeruKazu, waruKazu, result); } return result; } const result = factorial(num, waruKazuInit, []); console.log(result);
変数 num に 1536 を入力したときの結果。
[2, 2, 2, 2, 2, 2, 2, 2, 2, 3]
素因数分解の結果を格納する変数は、グローバル変数にするのが普通だと思うのですが、今回は関数に引数としてあたえて再帰するたびに渡すようにしてみました。関数型プログラミングっぽい?