トップページ⇒tech
1001コメント344KB

素数 "列挙" アルゴリズムを極めるスレ

■ このスレッドは過去ログ倉庫に格納されています
00011NGNG
メモリとかも考慮に入れた超高速なアルゴリズムを真剣に考えるスレ

既存のソフトも参考に挙げるべきか？
0002デフォルトの名無しさんNGNG
宿題？いや、卒業研究と言ったところか？
0003デフォルトの名無しさんNGNG
>>1
挙げるべきかじゃねーよ
スレ立てるなら参考ページからソフト、
関連技術などのリンクそろえておけ
0004デフォルトの名無しさんNGNG
暗号ソフトをつくるんじゃないのか？それを元に
0005デフォルトの名無しさんNGNG
>>1
既存スレ
　　　最速の素数判定アルゴリズム　　
http://pc.2ch.net/test/read.cgi/tech/993457354/

まだ使えるから　そっちでやってよ
00061NGNG
>>2
どっちでもないです。

>>3
申し訳なかったです。
ttp://www.google.co.jp/search?q=cache:FrIagBROO3QC:lt.sakura.ne.jp/~ryuca/pro/sosu/sosu.html+%91f%90%94+%83A%83%8B%83S%83%8A%83Y%83%80&hl=ja&start=8
↑キャッシュのみ生存
ttp://www.gt.sakura.ne.jp/~nyagy/integer/sosuu.html

素数算出系ソフト
http://www.lycos.co.jp/cgi-bin/pursuit?query=%91f%90%94&cat=jpdownload&maxhits=17&qs=gt|rate,gt|nflg
00071NGNG
>>5
判定と列挙は微妙に違います。向こうで書くと微妙にスレ違いになりそうだったので。
0008デフォルトの名無しさんNGNG
>>7　まあいいけど、　あっちのスレも半分以上は列挙の話題だよ
0009デフォルトの名無しさんNGNG
>>6
そこのリンク、ものすごく低レベルなんだが、
もしかして10桁とか20桁とかそういうものすごい低レベルな話？

数百万桁クラスの素数って事じゃないのか？
メモリ使用量も考慮してとかあるし。

リンクを見る限り、１自体がこの話題についてこれる気配がしないんだが
00101NGNG
>>9
そのとおりです。凄く低レベルです。
数百万桁クラスの素数を列挙する方法があるんですか？
0011デフォルトの名無しさんNGNG
>>10
作ったこともない奴が作った奴を批判する資格はない。
0012デフォルトの名無しさんNGNG
>>10 そんなもんがあったら驚天動地

列挙できるのは64bitでも限界に近いよ
00131NGNG
>>11
VBでなら一応あります(授業でですが)。
1億迄の素数を列挙するのに約10分(AMD K6-2 400MHz)という>>9が見ればクソかもしれませんが…
0014デフォルトの名無しさんNGNG
そこらへんは　フルイの使い方だけの問題だからなあ

どうせなら100桁（40バイト）くらいの素数を与えてそこから素数を列挙するとか
0015デフォルトの名無しさんNGNG
>>12
64bit限界はエラトステネスのふるいを使った場合
00161NGNG
>>14
100桁の素数辞書のサイズが莫迦にならないと思うんですが…
0017デフォルトの名無しさんNGNG
>>16 だから 指定した100桁程度の素数から 　28bit程度のフルイビットマップで表現すればいいでしょ？
0018デフォルトの名無しさんNGNG
>>15　他には巧い方法は無いと思うけど？　何かある？

まさか確率判定法でフルイを粗くさばく？
0019デフォルトの名無しさんNGNG
テーブル引き
0020デフォルトの名無しさんNGNG
32Bitの最大の素数って何？１個か２個素数がほしい。
0021デフォルトの名無しさんNGNG
2^32 - 5
0022デフォルトの名無しさんNGNG
もう１個欲しいなら　2^31 -1 も素数だから
0023デフォルトの名無しさんNGNG
じゃ課題を
n0 :=　170141183460469231731687303715884105727

n0　～ n0+0xffff の範囲の素数を列挙せよ
0024デフォルトの名無しさんNGNG
あれ？　もう１はヘタったの？

2^127-1 = 170141183460469231731687303715884105727
0025デフォルトの名無しさんNGNG
>>24　１ではないが　計算が終りません・・・(涙
0026デフォルトの名無しさんNGNG
>>1-all
てめえらここにソース出してみろ
0027デフォルトの名無しさんNGNG
CUBEって映画思い出した
0028デフォルトの名無しさんNGNG
>>26
ｵﾏｴﾓﾅｰって言ってほしい？
0029デフォルトの名無しさんNGNG
age
0030デフォルトの名無しさんNGNG
数値じゃなくて速さを極めるのでもいいの？
0031デフォルトの名無しさんNGNG
>>9のレベルが酷く低いとしか思えない…
それが可能なら現在のネットワーク社会が
おそらく崩壊するのだが…
0032デフォルトの名無しさんNGNG
速度、演算可能数値、コードの短さとかでも極める事には変わりない。

などと間口を広げてみるテスト。
0033房NGNG
素数ってな～に??
0034房NGNG
今、検索かけて調べたら

電子フロンティア財団(EFF)が、今までで最も大きな素数の発見に対して、最大25万ドルを提供しようとしている。

　問題は、誰も1人では賞金をもらうことはできないだろうということだ。

　この賞金を得られるほど大きな素数を発見するには、世界最速のスーパーコンピューターでも6万2000年かかると考えられている。

こんなことがあったYO
2chのみんなで25万㌦山分けｼﾏｯｼｮｲ!
0035デフォルトの名無しさんNGNG
>>34
最速の素数判定アルゴリズム
http://pc.2ch.net/test/read.cgi/tech/993457354/

ここはちょっと違うよー
0036デフォルトの名無しさんNGNG
平凡な素数判定って奇数をふるいにかけて残ったやつ、でよい？
プログラムの練習で書くような場合。
0037デフォルトの名無しさんNGNG
>>36
いいんじゃない？ てか俺それ以外に思いつかない。
0038デフォルトの名無しさんNGNG
列挙のばあい、倍数に非素数のマークつけるのはダメなの？
0039デフォルトの名無しさんNGNG
>>38
もちっと詳しく説明きぼんぬ。
0040デフォルトの名無しさんNGNG
http://pc.2ch.net/test/read.cgi/tech/1018840143/の改変

extern "C"{
int printf(const char*,...);
long atoi(const char*);
}

main(int c,char *v[]){
unsigned long m,q,r;

if(1<c){
m=atoi(v[1]);
char*P=new char[m];

for(q=3;q*q<m;q+=2){
if(P[q]!=1){
for(r=q*q;r<m;r+=q+q)
P[r]=1;
}
}

printf("2\n");
for(q=3;q<m;q+=2){
if(P[q]!=1)
printf("%u\n",q);
}
}
return 0;
}

これどうよ？
もっと短くできっか？
0041デフォルトの名無しさんNGNG
ageるぞ
0042デフォルトの名無しさんNGNG
>>40
> もっと短くできっか？
速度を気にしないならこんなのが７行スレにあったが。

#include <iostream.h>
int main(){for(int z,i=1;z=++i;){while(i%--z);if(z==1)cout<<i<<",";}return 0;}
0043デフォルトの名無しさんNGNG
>>42
それ最短極めたと思う。クソ遅いけどｗ

てわけで最短はこれでｹﾃｰｲ?
0044昔それ>>42書いた人NGNG
printf(char*,...);main(){int z,i=1;for(;z=i++;z?0:printf("%d,",i))while(i%z--);}
つーかスレ違い。

>>36,38
２から順に全部探してく方法だと、それが最速じゃないかな。
もっと条件を課してくと別のアルゴリズムがあるかもしれない。
俺はよく知らんけど…。
0045デフォルトの名無しさんNGNG
あげ
0046デフォルトの名無しさんNGNG
ttp://www.prime.net/prime.html
に63bit以下の素数全部載ってるよ
0047デフォルトの名無しさんNGNG
ページが見つかりません
検索中のページは、削除された、名前が変更された、または現在利用できない可能性があります。
0048デフォルトの名無しさんNGNG
　
0049デフォルトの名無しさんNGNG
age
0050デフォルトの名無しさんNGNG
>>48
つまんね
0051クレジャパンNGNG
素数てなんですか？>>1

0052ヽ(´ー｀)ノNGNG
プログラム言うより数学だろ
0053デフォルトの名無しさんNGNG
>>51
荒らしは氏ね

>>40のコード改善できないかな…漏れはもう触るとこがない気がするんだけど
0054デフォルトの名無しさんNGNG
>>53
速くするんだったらforループをq+=10とかにして
1の位が1、3、7、9のものだけ調べるとかじゃだめ？
難しいことわかんないけど。
0055デフォルトの名無しさんNGNG
>>54
ちょっとやってみよう
0056デフォルトの名無しさんNGNG
>>54
やってみようと言ったものの実行する前にふと気づく。
if(P[q]!=1){
で判定するから速さはあんまり変わらない気がする。
0057デフォルトの名無しさんNGNG
>>40　フルイを作る時は　テーブルの√最大値の迄で作れる

それから、そのコードでは32bitフルに素数を列挙出来ない。
列挙するにはビットマップでフラグを持ち
さらに 2と3の倍数を最初から除くようにする。

http://pc.2ch.net/test/read.cgi/tech/993457354/128
0058デフォルトの名無しさんNGNG
>>57
あっそうか！
自分が前に作ったのは小さい素数から順にファイルに保存してくやつだったから。。。
エラトステネス使ってたら意味ないか。。。
005958NGNG
>>56です
0060デフォルトの名無しさんNGNG
>>58 その
　　　最速の素数判定アルゴリズム　　
http://pc.2ch.net/test/read.cgi/tech/993457354/

のスレで既に話が出てると思うが、素数を保存する方法としても
整数として値保存するより、フルイをビットマップで保存する方が効率が良い
0061デフォルトの名無しさんNGNG
>>57
C初心者なのでソースが読めません…
006254NGNG
>>57
2,3の倍数だけじゃなくてほかの素数の倍数も除いとけば
プログラムのサイズは増えるけど速くなりますよね？
最速の素数判定アルゴリズムスレはレベル高くてちときつい･･･
0063デフォルトの名無しさんNGNG
こっちはもうちょいレベル低く行きましょう(^^;
実は>>40書いたの俺なんです…
0064デフォルトの名無しさんNGNG
>>62
除く処理がちと面倒…かな？
0065デフォルトの名無しさんNGNG
質問！
6の倍数に1足したら素数確定ですか？
0066デフォルトの名無しさんNGNG
>>65
25=6*4+1
0067デフォルトの名無しさんNGNG
あげ
0068デフォルトの名無しさんNGNG
この手があったか！？
ttp://f1.aaacafe.ne.jp/~pointc/log59.html

セコイのでsage
0069デフォルトの名無しさんNGNG
>>68
そのテーブルを作るプログラムを考えねば話にならんな。
ネタ募集あげ
0070デフォルトの名無しさんNGNG
Haskellだと

primes = sieve [2.. ] where
　　　　 sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]

だな。
0071デフォルトの名無しさんNGNG
>>68
「なんでもあり」なのに is_prime 使ってるのはなんでだろう？

while(n=next_prime()){
　　　　　　～
}
------
unsigned long next_prime()
{
　　　static const unsigned long *ptr = prime_table;
　　　return *ptr++;
}

でよくね？
0072デフォルトの名無しさんNGNG
実行ファイルのサイズがすごそう
小さい数字まで求めたいとき、プログラムのロード時間の方が大きくなって…
0073Delフサギコ ◆zE1iiRdQ NGNG
　　　　　 　 ∫ 　　　　　　　＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧ ∬　　　　 　 ／フォルダわけて分割したﾃｷｽﾄファイルを
　　 ミ,,ﾟДﾟノ,っ━~　　＜　　読み込んだ方がいいよ。
＿と~,,,　　~,,,ﾉ＿.　∀　　＼＿＿＿＿＿＿＿＿＿
　　　 .ﾐ,,,/~),　　.|　┷┳━
￣￣￣ .し'J￣￣|...　┃ 　どこまでか知らんが
￣￣￣￣￣￣￣ 　 .┻ 　素数列を32bitIntegerMaxまで持ったら256MBとか512MB
　　　　　　　　　　　　　　　程度のメモリが必要だったんじゃなかったかな。
0074デフォルトの名無しさんNGNG
>73
ということは、１００Ｍオーバーのアプリになるのか　ｲﾔﾝ
0075デフォルトの名無しさんNGNG
>>73
　2^32/ln(2^32) 　*4 -> 780MByte程
　2^31/ln(2^31) *4 -> 400MByte
0076デフォルトの名無しさんNGNG
>>65がいいトコついてるね。
2と3以外の素数はすべて6n±1に現れる。
0077デフォルトの名無しさんNGNG
>>68
ここでも素数バトルやってるみたい
ttp://haya.s5.xrea.com/cgi-bin/petit/petit.cgi
0078デフォルトの名無しさんNGNG
＞2と3以外の素数はすべて6n±1に現れる。

うん。
2以外の素数はすべて2n＋1に現れる。
2と3以外の素数はすべて6n±1に現れる。
そして2と3と5以外の素数はすべて30n±1, 30n±7, 30n±11, 30n±13,
30n±17, 30n±19, 30n±23に現れる。

だから？
0079デフォルトの名無しさんNGNG
>>78
何を勝ち誇ったように…
0080デフォルトの名無しさんNGNG
エラトステネシまんせー
0081デフォルトの名無しさんNGNG
よーし、パパも今日からp進Hodge理論を勉強しちゃうぞー
0082デフォルトの名無しさんNGNG
>>23
170141183460469231731687303715884105757 = n0 + 30
170141183460469231731687303715884105773 = n0 + 46
170141183460469231731687303715884105793 = n0 + 66
170141183460469231731687303715884105829 = n0 + 102
170141183460469231731687303715884105851 = n0 + 124
170141183460469231731687303715884105979 = n0 + 252
170141183460469231731687303715884106001 = n0 + 274
あといくつぐらいだろ。この割だと、1500こ前後だと思うけど。。。
0083デフォルトの名無しさんNGNG
最初のを
170141183460469231731687303715884105727 = n0 + 0
忘れてた。
0084デフォルトの名無しさんNGNG
2^16/ln(2^127) で 750個前後だと思う
0085デフォルトの名無しさんNGNG
>82
それ、試行的除算法ですか？
0086デフォルトの名無しさんNGNG
>>78
それだと 41 43 47 53 が重なる。
60n-30±x にして x=29 を追加。
0087デフォルトの名無しさんNGNG
>>76
それでどこが「いいトコついてる」のか教えてくれ。
0088デフォルトの名無しさんNGNG
言葉の綾
0089デフォルトの名無しさんNGNG
>>85
Miller 法です。
ですから Riemann 仮説が証明されないとこの結果も 100% 正しいとは
いえないのですが、現在のところほぼ間違いないといわれています。
私も証明はできないのですが、原理は簡単ですので、
興味がある方がいれば、原理だけなら、説明します。

さて、この範囲の探索に
pentium!!! 1.26GHz のマシンで4時間ほどかかりました。
結局、全部で 760 個の素数が見付かっています。
最後のは
170141183460469231731687303715884171179 = n0 + 65452
です。

Millwe 法で調べたので、これより多いことは
(私のプログラムミスが無いとすれば)ありません。
逆は Riemann 仮説が証明されるかにかかっています。
0090デフォルトの名無しさんNGNG
興味あります。教えてください。
0091デフォルトの名無しさんNGNG
>Riemann 仮説
Riemann予想(Riemann Hypothesis)のこと？
0092デフォルトの名無しさんNGNG
失礼しました。そうです、"Riemann 予想" でした。

Miller 法も、多分正確には "Miller-Rabin's Primality Test"
だとおもいます。以下、私の浅い理解レベルで解説してみます。
間違っていたら御指摘ください。

基本的にはフェルマーテストと、sqrt(1) が 1 or -1 である
ことをある範囲の数について確かめるのですが、この範囲が
Riemann Hypothesis が証明さればかなり狭い範囲でよいと言
うことです。

1. フェルマーテスト
フェルマーの小定理は、「p が素数なら、 0 以外のどんな a
についても、a^p \equiv a \pmod p」。(aをp乗してpで割った余り
がaになるってこと。この証明は簡単ですよね。)
さて、この命題の対偶は、(以下、TeXっぽい記号はよみにくいので
プログラム言語っぽく書きます。)
「ある a (!=0) について a^p%p が a でないならば、p は
素数ではない」。
です。そこで、ある数 p についてさまざまな a を持って来て
a^p%p を計算し、一つでも a にならない a があったらその時点で
p が素数ではないことが分かります。

ここで、注意ですが、1 <= a <=p-1 の全ての a について、
a^p%a=a になるのに、p が素数ではない場合があるってことです。

さらに捕捉ですが、a^p%p の計算は a, a^2%p, a^4%p, ... を作り
必要なのを掛け合わせます(%p しながら)。特に a や p が大きい
場合はそうしないと手間が極端に増加します。
0093デフォルトの名無しさんNGNG
ﾚｳﾞｪﾙ高いなー
0094デフォルトの名無しさんNGNG
>>93
や、実はその分野を勉強した人にとっては初歩の初歩なんよ。
専門分野が違う人に「おれって頭良いでしょ」とかますハッタリとしては
効果的なんだけどさ。
0095デフォルトの名無しさんNGNG
初等代数学の本に載っているから教養レベルだったかな
数学科だけかもしれないけど
0096デフォルトの名無しさんNGNG
>>94-95
そうなのか…ちょいと鬱だ
漏れはｴﾗﾄｽﾃﾈｽを2飛ばしでやるのが精一杯だYO...
0097デフォルトの名無しさんNGNG
保守
0098デフォルトの名無しさんNGNG
ageてみたり
0099Lisp 1.5NGNG
ちょと違う傾向で。

Haskellで書いた素数の無限リストのプログラム。

sieve (p : r) = p : sieve [ n | n <- r; n mod p ~= 0 ]
primes = sieve [2..]

:はconsの生成と分解。引数はパターンマッチング渡しで遅延評価。
一行目は、ZF記法っていう置換公理風のリスト生成。
二行目の[x..]は、[x, x+1, x+2, ...]というリスト生成。
0100デフォルトの名無しさんNGNG
>99
速さはいかほどでしょう？
0101Lisp 1.5NGNG
>>100
modの回数に関するO(n)は普通のエラトステネスの篩と同じです。
-- なこと、いわんでも分かってるか。(しかし何で素数判定法の話に…)
■ このスレッドは過去ログ倉庫に格納されています