素因数分解

2008/05/07(水)

　特に利用目的はないけれど、任意の数字を因数分解する、ちょっとしたお遊びプログラム。

　数学の世界では、素数の数列を記述する有効な方程式はまだ発見されていない。だから大きな桁の素数を掛け合わせた場合、その結果だけを用いて再び素因数分解するのは、たとえコンピュータといえど膨大な計算時間を必要とする。現在の暗号化技術はこれを利用しているので、もし万が一、素数列を記述する方程式が発見され、悪用されたら、世界中に大激震が走ることになる。

　まあ、そんな大それた話は別としても、７桁や８桁の数字でも、手計算では結構大変だ。たとえば、次の５つの数字が約数を持つかどうか、手計算で（電卓くらい使ってもいいけど）調べてみてください。

　　100000007、100000037、100639681、100639699、100639703

　実はこれらはどれも素数である（はずだ。……間違ってたら教えてください）。

　あるいはこんなのはどうか？　1010101 とか 101010101 といった数字。
　これはちゃんと因数分解できるけど、やっぱり手計算だと面倒くさい。結果は以下のとおり。

　　1010101 = 73 x 101 x 137
　　101010101 = 41 x 271 x 9091

　こんな約数になるなんて、まったく予測できないでしょう？　他にも、ぼくが面白いと思った素因数分解を、以下にあげておく。

　　11111 = 41 x 271
　　10101 = 3 x 7 x 13 x 37
　　111111 = 11 x 10101 = 3 x 7 x 11 x 13 x 37
　　1111111 = 239 x 4649
　　11111111 = 11 x 1010101 = 11 x 73 x 101 x 137
　　111111111 = 3 x 3 x 37 x 333667
　　1111111111 = 11 x 101010101 = 11 x 41 x 271 x 9091
　　1234567 = 127 x 9721
　　123456789 = 3 x 3 x 3607 x 3803
　　987654321 = 3 x 3 x 17 x 17 x 379721
　　100000001 = 17 x 5882353
　　1000000001 = 7 x 11 x 13 x 19 x 52579

　なんだか不思議な感じがしませんか？

　で、以上の計算はすべて下記のお遊びプログラムで発見したもの。やはり桁数が大きくなるほど処理に時間がかかって、タイムオーバーで結果が出なかったりもする。当然サーバへの負荷は大きいだろうから、レンタルサーバなどに設置するのは避けた方がいいでしょう。自分のＰＣで走らせて遊ぶ程度にとどめておくのが無難。計算仕様は、

最大処理時間(MET : max_execution_time)以上の計算は不可
2147483647 = 2^31-1 は int型の最大値（これより大きな数字は計算不可）
素数判定をするだけなら、とりあえず「2値に分解」できるかどうかで十分

　となってます。

factorization.php

<?php
mb_internal_encoding("UTF-8");
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <meta http-equiv="Content-Style-Type" content="text/css" />
  <title>factorization</title>
  <style type="text/css">
    body { font-family: 'Courier New'; }
    .Res { color: #f00; font-weight: bold; }
  </style>
</head>
<body>

<h1>因数分解プログラム</h1>

<p>※ 最大処理時間(MET:max_execution_time = <?php
   echo ini_get('max_execution_time');
?>sec.)以上の計算は不可<br />
※ 2147483647 = 2^31-1 は int型の最大値（これより大きな数字は計算不可）<br />
※ 素数判定をするだけなら、とりあえず「2値に分解」できるかどうかで十分</p>

<?php

$X = '';
$TextBoxValue = '';
if (isset($_POST['x'])) {
    $X = (int)$_POST['x'];
    if ($X <= 2147483647 && $X >= 0) {
        $TextBoxValue = $S = $X;
    } else {
        $NG = 1;
    }
}
$OPT = 0;
$CHK_Str = 'checked="checked"';
$CHK = array('', $CHK_Str);
if (isset($_POST['opt'])) {
    $OPT = (int)$_POST['opt'];
    if ($OPT === 1) {
        $CHK[0] = $CHK_Str;
        $CHK[1] = '';
    }
}
?>

<form method="POST" action="">
    <input type="text" id="x" name="x" value="<?php echo $TextBoxValue; ?>" />
    <input type="submit" value="計算" /><br />
    <input type="radio" id="opt" name="opt" value="1" <?php echo $CHK[0]; ?> />2値に分解   &nbsp;
    <input type="radio" id="opt" name="opt" value="0" <?php echo $CHK[1]; ?> />全値
</form>

<?php

$Result = '';

if (isset($S)) {
    if ($OPT === 1) {
        // 2値に分解
        // 2（唯一の偶素数として）
        if ($X % 2 === 0) {
            $X = $X / 2;
            $Result .= "2 ";
        } else {
        // 3以降の奇数
            for ($i = 3; $i < ($X / 2); $i += 2) {
                if ($X % $i === 0) {
                    $X = $X / $i;
                    $Result .= "{$i} ";
                    break;
                }
            }
        }
    } else { // ALL
        // 2（唯一の偶素数として）
        if ($X % 2 === 0) {
            while ($X % 2 === 0) {
                $X = $X / 2;
                if (!$Result) $Result .= "2 ";
                else $Result .= "x 2 ";
            }
        }
        // 3以降の奇数
        for ($i = 3; $i < ($X / 2); $i += 2) {
            if ($X % $i === 0) {
                while ($X % $i === 0) {
                    $X = $X / $i;
                    if (!$Result) $Result .= "{$i} ";
                    else $Result .= "x {$i} ";
                }
            }
        }
    }

    if (!$Result) $Result .= $X;
    elseif ($X !== 1) $Result .= "x {$X}";

    $Result = "{$S} = " . $Result;
} elseif (isset($NG) && $NG) {
    $Result = '入力値が 0 以下か、あるいは 2147483647 より大きいので計算できません';
} else {
    $Result = '&nbsp;';
}

?>

<hr />

<p class="Res"><?phpecho $Result;?></p>

<p class="Res"><?php
if (isset($S) && $S === $X && $S !== 1) {
    echo "{$S} は素数です。";
}
?></p>

</body>
</html>

　ちなみに、ぼくの環境では 537639701 と 2000777777 が素数かどうか確認できませんでした（入力値はもちろん単なる勘です）。素数かな？　さてどうでしょう。お暇な方はお試しください。素数の神秘がちょっとだけ体験できますよ、きっと。

Filed under: Sample | タグ: お遊び, 数学

Tail-Lagoon @ 13:56

コメントおよびトラックバック受付中です。
TB : http://weblogs.tail-lagoon.com/WebPC/2008/05/07/20/trackback/

コメントをどうぞ

この投稿へのコメントは RSS 2.0 フィードで購読できます。

ブログに検索機能をつけた（ver.2） | CakePHP 関連リンク |

PageUp

WEB + PC