最大の素数を出力する

2^20996011-1

手持ちの処理系でこれを出力できたのは Mathematica だけ。

2^20996011-1 >> temp.txt

スクリプトもいたってシンプル…なのはあまり関係ないかしらん。--sumim

えっと...つまり、この素数を印字してみるべや、って話なのですね。十進数でおよそ7000000桁ですか。文字列を保持するだけで７MByteくらいのメモリが必要？。スペックの時点で、UBASICでも出力不可能な感じですね。--CUE

ちなみに、どんなパソコンでも（8ビットマイコンでも）メモリさえあれば計算は瞬時に行えます：なぜなら、ビット1を20996011個並べる（最上位の１バイトが07Hで、残りの下位2624501バイトが0FFH）だけなので。--CUE
ついでに、10で割った余りはどの程度のスピードで求められるのか、考えてみました。剰余類の理論により、モジュロ同士の加減乗除は加減乗除のモジュロと等しいので、６×６≡６(mod 10)を利用して、十六進数表現で~~「全桁」~~「最下位桁を除く全ての桁」の数字の総和を求めて(16でなくても、16の累乗、つまり４の倍数ビットならなんでもいいので、例えば32ビットの「桁」でもいい)、６倍して最下位桁を加えてから１０で割った余りを求めたものと等しくなると思います。この理屈でいけば、20996011は4で割ると3余るので、８×６－１≡７(mod 10)と簡単に暗算できて、１の位は「７」になると思いますが、あってますか？--CUE

↑ rubyでもSqueakでも(下記の逆順プログラムで) 7,4,0,2…などと出ますので、(こっちの間違いじゃない限り)OKです --戯

Ruby (Cygwin)

open('temp.txt','w') {|f| f.print(2**20996011-1)}

返ってきません。ただ、Ruby が優秀なのは、

print((2**20996011-1).modulo(10))

をほぼ瞬時で返すことですね。

a=(2**20996011-1); while a!=0 do p(a % 10); a/=10; end

(下から1桁づつ表示する)は、Crusoe600MHzでは2桁/秒くらいの速度で淡々と表示されるようです(時折GCでワンテンポ止まるけど)。つまりこれが延々と続くわけですね。最初の数百桁までしか見てないけど、この計算のしかただと処理時間が後半加速的に遅くなるってことは無い(よね？)ので、後は待つだけ。「返って来ない」のは待てなかっただけかも(^^;
なお、10を10000に替えても同じようなもんですが、1000000000とかにするとかなり遅くて怪しげ。rubyだと特に1回の諸々の演算が出来るだけ31bitで収まるかどうかで随分かわる筈。--戯

Smalltalk (Squeak)

| file |
file := FileStream fileNamed: 'temp.txt'.
[(2 raisedTo: 20996011) - 1 printOn: file] ensure: [file close]

返ってきません。(2 raisedTo: 20996011) - 1 の do it は数秒なので、計算は終えているのですが、十進文字列化がだめなようです。

(2 raisedTo: 20996011) - 1 \\ 10

はちょっと待たされますが返ってはきます。

Squeakでも「1桁づつ出す」をやってみた…つもりなのですが、どっか間違えたらしく全然返ってこないし、
＃正しいコードは誰かヨロシクね。
Imageファイルが100Mに膨れちゃった(迂闊にもSaveしてしまったんです)し、そのImageで再び起動できなくなっちゃったっぽい。
ここ数日のImageをBackupしてなかったんで、数日の作業結果(些細とはいえ)を捨てる羽目になっちゃった(T_T)。
ところで、なぜ「Imageが」膨れたのかは興味深いです。確かに計算結果は巨大オブジェクトになりますが、
あの書き方だとオブジェクトはすぐに参照件数0になって破棄されそうな気がするんですが… --戯

正しくは

a:=(2 raisedTo: 20996011) - 1.
[a>0] whileTrue: [ Transcript show: (  a\\10 ).  a := a // 10.  ].

みたいな感じ(これは動きます) --戯

Haskell (Win-Hags98)

writeFile "temp.txt" (show (2^20996011-1))

mod (2^20996011-1) 10

ともに ERROR - Garbage collection fails to reclaim sufficient space が生じます。

Scheme (Cgywin-guile)

(call-with-output-file "temp.txt" 
	(lambda (p) (display (- (expt 2 20996011) 1) p)))

(modulo (- (expt 2 20996011) 1) 10)

ともに Memory allocation error が生じます。--sumim

このページを編集 (3888 bytes)

以下の 2 ページから参照されています。

適当なリンク先が見あたらないページを作るための場所　最終更新: 2023-08-01, 22:54:59 <p229223>
この一行は絶対無二の一行なり　最終更新: 2006-05-21, 17:08:58 <p13168->

This page has been visited 6172 times.