「大きな数の因数分解」についての考察。いま「大きな数の因数分解」というキーワードをgoogleに入れたらおととい20070301のわたしのはてなの日記http://d.hatena.ne.jp/niming538/20070301がヒットしてしまいました。（大きな数の素因数分解とすべきだったかもしれない。）
となるとちょっと責任を感じて、すこし考察と解説をします。
１．普通パソコンやプログラム言語では大きな自然数が扱えません。大きなというのは100桁とかですね。10e200とかいう表記があるので一見扱える気がしますが、そのうち途中までしか正しくない。これではたとえば10の300剰を9801で割ったらどんな循環数になるかとか、ごく普通の数に対する疑問を解くことすらできません。
２．LispとかRubyとかはどうやっているのかわかりませんが、むちゃくちゃ長い数を扱えます。掛け算割り算だとかるく数百桁いけると思います。たぶん中は文字列で持っているのだろうと想像しています。
３．因数分解、素因数分解はさらに難しい課題で、ある数が素数かどうかというのはその数以下の数で割って余りがない、ということを証明しなければなりません。2から順番に割ってみるわけですが、それに0.1秒しかかからないとしてもあるレベル以上の桁数になると時間的に無理になります。
そこでいろんな効率的な方法が考えられています。
４．エラトステネスの篩（ふるい）というのはいったんその数を配列にしてしまって、2で割れるものを消す、3で割れるものを消す、4はもう消えているので、次は5で割れるものを消すという風に、順次篩（ふるい：網のようなもので砂から石ころを除去するような道具）にかけていく。ちなみに英語でふるいはsieveです。
５．大きな数が素数かどうかを調べるのにすべての素数を割り出す必要はなくて、その数のルート（二乗根）までの素数で調べてみればいい。ルートより大きい数で割り切れる場合、その商はルートより小さい数だから、ありえない。
６．上記の理屈で作られているのが、使っているrubyプログラムで、これはgoogleで因数分解（factorization）、ruby, sieve of eratosthenesなどで探したサイトにありました => Daniel Pearson's Diary,http://www.nanoo.org/diary/computing/index.html
７．このプログラムに大きな数を入れると、どこでひっかかるかというとルートを出すところは問題なくて、そのルートをいったん配列にするところ（to_a）でメモリー不足になりました。
８．ここで考えたのが、この配列は「いったん」作るだけで、そのうち使うのはその中の素数だけですし、一度ふるいにかけて、さらに目的の数字の約数でないものは二度と使いませんので、ほんとはこんなに大きいものは不要。だったらたとえば10の5剰までなら一瞬で扱えるのならその数までの数で目的の数を割ってみて、割れるようだったら目的の数自体を小さくしていける。割れないようだったら、順次素数だけの配列を作って行き、目的の数のルートまでたどり着くまで繰り返す。それでも割り切れなかったら素数。
９．たぶんrubyならこの手順もプログラム化できると思いますが、今回の課題はそこまで行かずに答えが出てしまったので、これは宿題。
以上
