1億番目の素数


R言語のこと調べていて、そう言えばと思い出したのがMathematica。マセマティカ自体は高いので企業や学校でしか使えないと思うけど、Wolframリサーチのサイトがすごいですよね。数学関係の記事の宝庫になっていると思う。Mathematicaを買わなくてもこのサイトは読めるので、参考になります。きょうは素数というキーワードで検索をかけたらMathematicaでは10億番目の素数を求める、というような場合のためのPrimeという関数があります、と書いてあった。
10億番目というのがさすがMathematicaで、とりあえずJ言語ではどうかとやってみました。

   p:10^9
limit error
p:10^9
p:10^8 2038074751

ほう、10億ではエラーになるけど、1億なら大丈夫! 貧乏人のMathematicaとしては健闘していると思う。それにMathematicaだってわたしのマシンに入れたらどうなるかわからないし。

少し実験。この素数を掛けたり、掛けた結果を素因数分解できるかどうか。

   x=: x: p:10^8    NB.拡張整数にする
   x: x ^ 2   NB.二乗する
4153748690663712001   NB.オッケー
   q: x: x ^ 2   NB.q:で素因数分解を試みる
nonce error NB.nonce errorとは?
q:x:x^2
": x 2038074751 $ ": x NB.文字列にしてシェイプをみると桁数がわかります 10 x * 10^9x 2038074751000000000 x * (10^9x) - 1 NB.10億ひく1をxに掛けてみる 2038074748961925249 q: x * (10^9x) - 1 NB.素因数分解は簡単に成功! 3 3 3 3 37 333667 2038074751 q: x * (10^10x) - 1 3 3 11 41 271 9091 2038074751 q: x * (10^20x) - 1 3 3 11 41 101 271 3541 9091 27961 2038074751 q: x * (10^30x) - 1 3 3 3 7 11 13 31 37 41 211 241 271 2161 9091 2906161 2038074751

1億番目の素数の二乗を素因数分解しようとしたらエラーになったけど、それよりはるかに大きな数の素因巣分解ができることから、数の大きさや桁数が問題なのではなくて、含まれる素数の大きさが障害になっているだろうことが想像できます。ちなみに10^30xでは1秒ほど待ちました。

誰か他の言語でやってみてくれないかしら。