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

■掲示板に戻る■ ■過去ログ倉庫めにゅーに戻る■

1 名前： 素数マニア 投稿日： 2001/04/23(月) 07:16: 素数を例えば100万桁求めたいときはどういうプログラム書いたらいい?
int限界までなら簡単だけどもっと、たとえば100万桁まで求めるなら??
しかも計算速度を上げるテクニックなんかは???
C/C++で希望
2 名前： デフォルトの名無しさん 投稿日： 2001/04/23(月) 07:32: 宿題は自分でやれ
3 名前： えらとすてねす 投稿日： 2001/04/23(月) 11:36: ふるい
4 名前： デフォルトの名無しさん 投稿日： 2001/04/23(月) 11:47: 10^1000000bitのメモリが最低限必要だな。
5 名前： デフォルトの名無しさん 投稿日： 2001/04/23(月) 14:40: 変数を変数一つのbit幅進数の一桁として、配列で数値を表現すればできるよ。
32bit変数であれば、100万桁は、10000000 / log10(2^32) = 1038000 で、4MBのメモリで表現
できる。

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

長桁計算のルーチンを最適化するのが楽しいんだけれどね。
頑張って下さい。
6 名前： 1です 投稿日： 2001/04/24(火) 03:06: >>2
残念、宿題じゃないんだな。
ただ、こういう面白い宿題出してくれる学校って行きたいよなー。

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

>>5
サンクス、そーか、長桁計算で検索か、方法の名前がわからんくて
「多桁計算」で検索してもあんまりヒットしなかったから2chに書いてみたす。
じゃちびっと調べてきてみます。
7 名前： 4だが 投稿日： 2001/04/24(火) 08:04: 「ふるい」を実現するためには、って意味ね。<10^1000000bit
8 名前： 5 投稿日： 2001/04/25(水) 23:31: >>7
ふるいでも、10000000bit あれば済むかと。
なんで、10^1000000 なんだろ。

それに、1000000 だと、「100万」までしか表現できないから、「100万桁」とは違う。
900万だって、100万桁だい。
9 名前： デフォルトの名無しさん 投稿日： 2001/04/26(木) 00:55: 100万桁だよ？　10^10000000ですよ？

結局全部を網羅するにはふるいが良いんじゃないかなぁ…
特定の数字を素数かどうか判定するアルゴリズムは結構あるけど。
10 名前： デフォルトの名無しさん 投稿日： 2001/04/26(木) 00:58: >>9
ふるいだと桁の話がでてくるよね？
全部を網羅するなんていったら……
11 名前： デフォルトの名無しさん 投稿日： 2001/04/26(木) 00:59: やっぱ素数を数えて落ち着きたいのか？ >>1
12 名前： 10 投稿日： 2001/04/26(木) 01:03: ああ、なんか的外れなこと言ったかな……
ちゃんと上のほう読んでなかった。
なんかゴメン>>9

>>8
桁と位の違いわかるかぁ？
13 名前：投稿日：