トップページ⇒tech
13コメント3KB

素数を無限大に早く求めるプログラムを作ろう

■ このスレッドは過去ログ倉庫に格納されています
0001素数マニアNGNG
素数を例えば100万桁求めたいときはどういうプログラム書いたらいい?
int限界までなら簡単だけどもっと、たとえば100万桁まで求めるなら??
しかも計算速度を上げるテクニックなんかは???
C/C++で希望
0002デフォルトの名無しさんNGNG
宿題は自分でやれ
0003えらとすてねすNGNG
ふるい
0004デフォルトの名無しさんNGNG
10^1000000bitのメモリが最低限必要だな。
0005デフォルトの名無しさんNGNG
変数を変数一つのbit幅進数の一桁として、配列で数値を表現すればできるよ。
32bit変数であれば、100万桁は、10000000 / log10(2^32) = 1038000 で、4MBのメモリで表現
できる。

具体的なやり方は、"長桁計算"とか"多倍長計算"で検索してみましょう。
楽したければ、GNU MP とかのlibraryつかっちゃうとか。

長桁計算のルーチンを最適化するのが楽しいんだけれどね。
頑張って下さい。

00061ですNGNG
>>2
残念、宿題じゃないんだな。
ただ、こういう面白い宿題出してくれる学校って行きたいよなー。

>>3
うまいかけ言葉!!
確かにねた的に古いとおもうんだけど古いから何か洗練されたテクがあるのかなと。

>>5
サンクス、そーか、長桁計算で検索か、 方法の名前がわからんくて
「多桁計算」で検索してもあんまりヒットしなかったから2chに書いてみたす。
じゃちびっと調べてきてみます。
00074だがNGNG
「ふるい」を実現するためには、って意味ね。<10^1000000bit
00085NGNG
>>7
ふるいでも、10000000bit あれば済むかと。
なんで、10^1000000 なんだろ。

それに、1000000 だと、「100万」までしか表現できないから、「100万桁」とは違う。
900万 だって、100万桁だい。
0009デフォルトの名無しさんNGNG
100万桁だよ？　10^10000000ですよ？

結局全部を網羅するにはふるいが良いんじゃないかなぁ…
特定の数字を素数かどうか判定するアルゴリズムは結構あるけど。
0010デフォルトの名無しさんNGNG
>>9
ふるいだと桁の話がでてくるよね？
全部を網羅するなんていったら……
0011デフォルトの名無しさんNGNG
やっぱ素数を数えて落ち着きたいのか？ >>1
001210NGNG
ああ、なんか的外れなこと言ったかな……
ちゃんと上のほう読んでなかった。
なんかゴメン>>9

>>8
桁と位の違いわかるかぁ？
0013NGNG
NG
■ このスレッドは過去ログ倉庫に格納されています