2013年1月14日
ある数を素数の積の形で表すことを「素因数分解」と言う。素数でない自然数は、すべて「合成数」なので、素因数分解ができることになる(ただし、「1」の素因数分解は「1」とする）。
例えば「12345」を素因数分解する手順を考えてみる。1の位が「5」なので、「2」で割ると余りが出てしまう。そこで「3」で割ってみる。「12345÷3＝4115」で割りきることができた。続けて、その商を割る「4115÷3＝1371.666…」とすると、割り切れないので、次の素数「5」で割ってみる。「4115÷5＝823」となった。
ここまでで「12345＝3*5*823」と表すことができた。ところが「823」を「7」で割っても「11」で割っても余りが出てしまう。いったい、どこまで素数で割り続けなければならないのか。「12345」の平方根を求め、小数点以下を切り捨て、自然数にすると「111」。「111」は合成数だが、111以下の最大の素数まで調べればよい。
「111」以下の素数では「109」が最大。109×109＝11881、次の素数「113」だと、「113×113＝12769」と「12345」より大きな数になってしまう。それより大きな素数は調べなくてもよいとゆーことね。
で、結局「109」まで調べたとしても「823」を割り切れる数は存在しない。なぜなら「823」は素数だからだ。つまり「12345＝3*5*823」で素因数分解は完了していたわけ。素因数分解は、互いに素な数の積の形で表せられる。積の交換法則は成り立つが、その一意性が担保されている。つまり、ある自然数を素因数分解すると、たったひと通りに定まり、これ以外の素因数分解の形は存在しない！（キッパリ）
■JavaScript
<script>
function factorize() {
var X = document.myFORM.myValue.value;
var sqrX = Math.sqrt(X);
var ans = "";
var Answer = "";
for (i=2; i <= sqrX; i++) {
if ((X % i)==0) {
n=0;
do {
n++;
X = X / i;
} while ((X % i)==0);
if (n==1) {
ans += "＊"+ i;
} else if (n >1) {
ans += "＊"+ i +"＾"+ n ;
}
}
}
if (X > sqrX) {
ans += "＊"+ X;
}
ans = ans.substring(1);
Answer = "＝ "+ ans;
document.getElementById("result").value = Answer;
}
</script>
■HTML
<form name="myFORM"> <input type="text" name="myValue" value="12345"> <input type="button" value=" 素因数分解 " onclick="factorize()"><br /> <input type="text" id="result" value=""> </form>