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

メモリとかも考慮に入れた超高速なアルゴリズムを真剣に考えるスレ

既存のソフトも参考に挙げるべきか？

宿題？いや、卒業研究と言ったところか？

>>1
挙げるべきかじゃねーよ
スレ立てるなら参考ページからソフト、
関連技術などのリンクそろえておけ

暗号ソフトをつくるんじゃないのか？それを元に

>>1
既存スレ
　　　最速の素数判定アルゴリズム　　
http://pc.2ch.net/test/read.cgi/tech/993457354/

まだ使えるから　そっちでやってよ

>>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

>>5
判定と列挙は微妙に違います。向こうで書くと微妙にスレ違いになりそうだったので。

>>7　まあいいけど、　あっちのスレも半分以上は列挙の話題だよ

>>6
そこのリンク、ものすごく低レベルなんだが、
もしかして10桁とか20桁とかそういうものすごい低レベルな話？

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

リンクを見る限り、１自体がこの話題についてこれる気配がしないんだが

>>9
そのとおりです。凄く低レベルです。
数百万桁クラスの素数を列挙する方法があるんですか？

>>10
作ったこともない奴が作った奴を批判する資格はない。

>>10 そんなもんがあったら驚天動地

列挙できるのは64bitでも限界に近いよ

>>11
VBでなら一応あります(授業でですが)。
1億迄の素数を列挙するのに約10分(AMD K6-2 400MHz)という>>9が見ればクソかもしれませんが…

そこらへんは　フルイの使い方だけの問題だからなあ

どうせなら100桁（40バイト）くらいの素数を与えてそこから素数を列挙するとか

>>12
64bit限界はエラトステネスのふるいを使った場合

>>14
100桁の素数辞書のサイズが莫迦にならないと思うんですが…

>>16 だから 指定した100桁程度の素数から 　28bit程度のフルイビットマップで表現すればいいでしょ？

>>15　他には巧い方法は無いと思うけど？　何かある？

まさか確率判定法でフルイを粗くさばく？

テーブル引き

32Bitの最大の素数って何？１個か２個素数がほしい。

2^32 - 5

もう１個欲しいなら　2^31 -1 も素数だから

じゃ課題を
n0 :=　170141183460469231731687303715884105727

n0　〜 n0+0xffff の範囲の素数を列挙せよ

あれ？　もう１はヘタったの？

2^127-1 = 170141183460469231731687303715884105727

>>24　１ではないが　計算が終りません・・・(涙

>>1-all
てめえらここにソース出してみろ

CUBEって映画思い出した

>>26
ｵﾏｴﾓﾅｰって言ってほしい？

age

数値じゃなくて速さを極めるのでもいいの？

>>9のレベルが酷く低いとしか思えない…
それが可能なら現在のネットワーク社会が
おそらく崩壊するのだが…

速度、演算可能数値、コードの短さとかでも極める事には変わりない。

などと間口を広げてみるテスト。

素数ってな〜に??

今、検索かけて調べたら

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

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

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

こんなことがあったYO
2chのみんなで25万�j山分けｼﾏｯｼｮｲ!

>>34
最速の素数判定アルゴリズム
http://pc.2ch.net/test/read.cgi/tech/993457354/

ここはちょっと違うよー

平凡な素数判定って奇数をふるいにかけて残ったやつ、でよい？
プログラムの練習で書くような場合。

>>36
いいんじゃない？ てか俺それ以外に思いつかない。

列挙のばあい、倍数に非素数のマークつけるのはダメなの？

>>38
もちっと詳しく説明きぼんぬ。

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;
}

これどうよ？
もっと短くできっか？

ageるぞ

>>40
> もっと短くできっか？
速度を気にしないならこんなのが７行スレにあったが。

#include <iostream.h>
int main(){for(int z,i=1;z=++i;){while(i%--z);if(z==1)cout<<i<<",";}return 0;}

>>42
それ最短極めたと思う。クソ遅いけどｗ

てわけで最短はこれでｹﾃｰｲ?

printf(char*,...);main(){int z,i=1;for(;z=i++;z?0:printf("%d,",i))while(i%z--);}
つーかスレ違い。

>>36,38
２から順に全部探してく方法だと、それが最速じゃないかな。
もっと条件を課してくと別のアルゴリズムがあるかもしれない。
俺はよく知らんけど…。

あげ

ttp://www.prime.net/prime.html
に63bit以下の素数全部載ってるよ

ページが見つかりません
検索中のページは、削除された、名前が変更された、または現在利用できない可能性があります。

　

age

>>48
つまんね

素数てなんですか？>>1

プログラム言うより数学だろ

>>51
荒らしは氏ね

>>40のコード改善できないかな…漏れはもう触るとこがない気がするんだけど

>>53
速くするんだったらforループをq+=10とかにして
1の位が1、3、7、9のものだけ調べるとかじゃだめ？
難しいことわかんないけど。

>>54
ちょっとやってみよう

>>54
やってみようと言ったものの実行する前にふと気づく。
if(P[q]!=1){
で判定するから速さはあんまり変わらない気がする。

>>40　フルイを作る時は　テーブルの√最大値の迄で作れる

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

http://pc.2ch.net/test/read.cgi/tech/993457354/128

>>57
あっそうか！
自分が前に作ったのは小さい素数から順にファイルに保存してくやつだったから。。。
エラトステネス使ってたら意味ないか。。。

>>56です

>>58 その
　　　最速の素数判定アルゴリズム　　
http://pc.2ch.net/test/read.cgi/tech/993457354/

のスレで既に話が出てると思うが、素数を保存する方法としても
整数として値保存するより、フルイをビットマップで保存する方が効率が良い

>>57
C初心者なのでソースが読めません…

>>57
2,3の倍数だけじゃなくてほかの素数の倍数も除いとけば
プログラムのサイズは増えるけど速くなりますよね？
最速の素数判定アルゴリズムスレはレベル高くてちときつい･･･

こっちはもうちょいレベル低く行きましょう(^^;
実は>>40書いたの俺なんです…

>>62
除く処理がちと面倒…かな？

質問！
6の倍数に1足したら素数確定ですか？

>>65
25=6*4+1

あげ

この手があったか！？
ttp://f1.aaacafe.ne.jp/~pointc/log59.html

セコイのでsage

>>68
そのテーブルを作るプログラムを考えねば話にならんな。
ネタ募集あげ

Haskellだと

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

だな。

>>68
「なんでもあり」なのに is_prime 使ってるのはなんでだろう？

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

でよくね？

実行ファイルのサイズがすごそう
小さい数字まで求めたいとき、プログラムのロード時間の方が大きくなって…

　　　　　 　 ∫ 　　　　　　　＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧ ∬　　　　 　 ／フォルダわけて分割したﾃｷｽﾄファイルを
　　 ミ,,ﾟДﾟノ,っ━~　　＜　　読み込んだ方がいいよ。
＿と~,,,　　~,,,ﾉ＿.　∀　　＼＿＿＿＿＿＿＿＿＿
　　　 .ﾐ,,,/~),　　.|　┷┳━
￣￣￣ .し'J￣￣|...　┃ 　どこまでか知らんが
￣￣￣￣￣￣￣ 　 .┻ 　素数列を32bitIntegerMaxまで持ったら256MBとか512MB
　　　　　　　　　　　　　　　程度のメモリが必要だったんじゃなかったかな。

>73
ということは、１００Ｍオーバーのアプリになるのか　ｲﾔﾝ

>>73
　2^32/ln(2^32) 　*4 -> 780MByte程
　2^31/ln(2^31) *4 -> 400MByte

>>65がいいトコついてるね。
2と3以外の素数はすべて6n±1に現れる。

>>68
ここでも素数バトルやってるみたい
ttp://haya.s5.xrea.com/cgi-bin/petit/petit.cgi

＞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に現れる。

だから？

>>78
何を勝ち誇ったように…

エラトステネシまんせー

よーし、パパも今日からp進Hodge理論を勉強しちゃうぞー

>>23
170141183460469231731687303715884105757 = n0 + 30
170141183460469231731687303715884105773 = n0 + 46
170141183460469231731687303715884105793 = n0 + 66
170141183460469231731687303715884105829 = n0 + 102
170141183460469231731687303715884105851 = n0 + 124
170141183460469231731687303715884105979 = n0 + 252
170141183460469231731687303715884106001 = n0 + 274
あといくつぐらいだろ。この割だと、1500こ前後だと思うけど。。。

最初のを
170141183460469231731687303715884105727 = n0 + 0
忘れてた。

2^16/ln(2^127) で 750個前後だと思う

>82
それ、試行的除算法ですか？

>>78
それだと 41 43 47 53 が重なる。
60n-30±x にして x=29 を追加。

>>76
それでどこが「いいトコついてる」のか教えてくれ。

言葉の綾

>>85
Miller 法です。
ですから Riemann 仮説が証明されないとこの結果も 100% 正しいとは
いえないのですが、現在のところほぼ間違いないといわれています。
私も証明はできないのですが、原理は簡単ですので、
興味がある方がいれば、原理だけなら、説明します。

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

Millwe 法で調べたので、これより多いことは
(私のプログラムミスが無いとすれば)ありません。
逆は Riemann 仮説が証明されるかにかかっています。

興味あります。教えてください。

>Riemann 仮説
Riemann予想(Riemann Hypothesis)のこと？

失礼しました。そうです、"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 が大きい
場合はそうしないと手間が極端に増加します。

ﾚｳﾞｪﾙ高いなー

>>93
や、実はその分野を勉強した人にとっては初歩の初歩なんよ。
専門分野が違う人に「おれって頭良いでしょ」とかますハッタリとしては
効果的なんだけどさ。

初等代数学の本に載っているから教養レベルだったかな
数学科だけかもしれないけど

>>94-95
そうなのか…ちょいと鬱だ
漏れはｴﾗﾄｽﾃﾈｽを2飛ばしでやるのが精一杯だYO...

保守

ageてみたり

ちょと違う傾向で。

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

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

:はconsの生成と分解。引数はパターンマッチング渡しで遅延評価。
一行目は、ZF記法っていう置換公理風のリスト生成。
二行目の[x..]は、[x, x+1, x+2, ...]というリスト生成。

>99
速さはいかほどでしょう？

>>100
modの回数に関するO(n)は普通のエラトステネスの篩と同じです。
-- なこと、いわんでも分かってるか。(しかし何で素数判定法の話に…)

では、新しい問題を提案。

2番目の素数を求めよ　（答え　3）
22番目の素数を求めよ　（答え　79）
222番目の素数を求めよ　（答え　1399）

という具合に 2…2番目の素数を求めよ。

N番目の素数を求めるには、それ以下の素数を全て列挙する以外方法はないだろう。
まぁ、10の整数乗番目の素数はweb 上にけっこう落ちているから、
それを利用すれば多少は処理を速くできる。

>>102

2222番目=19583
22222番目=252233
222222番目=3080969

とりあえず、ここまで求めた

素数表現多項式ってあるの知ってる人紹介キボン
確か２変数の多項式で、整数の値を入れた時、値が正になる限り素数
だったような...
全部求められなくとも、巨大な素数をいち早く見つける方法としては
有効かも.

>>104
prime generate polynomial で検索してみた。
見つかったのは、ものすごい26変数の多項式だけですた。
http://mathworld.wolfram.com/PrimeDiophantineEquations.html
こんな連立方程式とても解けねーっす。

age

漏れら極悪非道のageブラザーズ！
今日もネタもないのにageてやるからな！
￣￣∨￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
∧＿∧　∧＿∧　　age
（・∀・∩）（∩・∀・）　　age
（つ　丿 （　 ⊂） age
（ ヽノ　ヽ/　）　 age
し（＿）　（＿）Ｊ

　　　最速の素数判定アルゴリズム　　
http://pc.2ch.net/test/read.cgi/tech/993457354/

このスレ落ちちゃったか・・・・

保守

このプログラムは優れているのか？　鑑定求む
ttp://www.klic.org/software/klic/lang/node134.html#SECTION008100000000000000000

現在、>>65 >>76 >>78 の路線でちょっと作ってみてます。

>>110 エラトステネス。
Ｃの配列の練習問題との違いは、素数であることが確定したら
すぐ出力されること。

>>111
がんがってくれ。健闘を祈る。

うーん、>>65 >>76 >>78の発展を「だから？」の煽りに負けず繰り返させて、
「素数でないものを初めから入力列から省き、効率的にエラトステネスを行う」
ということを実現したのだが……。

E:\>primes 100
Target: 100　 　 　 　 　 　 Time　 : 0sec
numOfPreSieved: 26　 　 　 numOfFalsePrime: 3　 　 　 Fail Rate: 11.5385%

E:\>primes 1000
Target: 1000　 　 　 　 　 　 Time　 : 0sec
numOfPreSieved: 261　 　 numOfFalsePrime: 95　 　 Fail Rate: 36.3985%

E:\>primes 10000
Target: 10000　 　 　 　 　 Time　 : 0sec
numOfPreSieved: 2566　 　 numOfFalsePrime: 1339　 Fail Rate: 52.1824%

E:\>primes 100000
Target: 100000　 　 　 　 　 Time　 : 0.046sec
numOfPreSieved: 25623　 numOfFalsePrime: 16033　 Fail Rate: 62.5727%

E:\>primes 1000000
Target: 1000000　 　 　 　 Time　 : 0.765sec
numOfPreSieved: 256213　 numOfFalsePrime: 177717 Fail Rate: 69.363%

E:\>primes 10000000
Target: 10000000　 　 　 　 　 　 　 　 Time　 : 16.593sec
numOfPreSieved: 2562069 numOfFalsePrime: 1897492　 　 　 　 Fail Rate: 74.0609%

だんだんFail Rateが上昇してます。
つまり、本当の勝負である億以上の世界では意味が無くなってきているわけで……。
STL Listを使ったオーバーヘッドで、多分普通のエラトステネスに負けるでしょう。

ちなみに上記の時間はメモリ内にListで素数列を展開した時の時間です。
Pen4 1.6GHz / DDR-SDRAM 512 MBytes / Windows 2000 です。

ttp://f1.aaacafe.ne.jp/~zxrg/software/psrch.html
ここ参考になるかな？

このソースの鑑定求む
http://www.kurims.kyoto-u.ac.jp/~ooura/pc_bench/prime.c

>116
エラトステネスだろう。ビット演算多用してるので早そうだ
ただ　make_prime_tab 中の k <= nh / 3 がよくわからん。

>117
２と３の倍数をはじいてるからか？

>>116のコードが理解できない…

保守

age

　

もはや多項式時間なので、ハードウェアの進歩を待つのが吉というデフレスパイラル

>>117
sqrt()や乗算を使いたくなかったのだろう。
ビットを多用しているのはメモリ節約の為(1/32か)。
普通にエラトステネスの篩を使った場合と比べて速くなるかは微妙だな。

例のインドアルゴリズムがこのスレの存在価値を失わせた
訳ではない、とここにも書いておきます。
（私自身は前回のがそれほど効率的でなかったことに気づき
やる気喪失ですが。やるなら2,3の倍数を飛ばすエラトステネスを
お勧めします)

現状まとめ（違ってたら訂正よろしくお願いします）：
判定と列挙は別、それに確率的判定なら今まででも出来たし、
現段階ではまだ決定的判定は多項式時間といえど遅すぎる。

2と3の倍数を飛ばすエラトステネスは結構速くなるね。

ところで◆.RANK1Kg氏、下のコードはどうでしょうか？
http://idm.s9.xrea.com/factorization/impl/eratosthenes/esieve4.c

インドアルゴリズムを改良すれば論文にできるね。

ひぇっ、指名されたｗ

速いですねー。しかもファイル出力まで作っちゃうし。
関連記事も読み応えあります。
挑戦する人は必読かもしれません。

私のは「根本的にオーダが改善する」期待があったので、
実際の時間よりオーダを気にしていた……と言い訳させてください。
（ちょっと考えればそんなことは無いことは分かったのですが、
私の数学力だと実際に作って確かめなければ分からなかった）

素数判定に使われるアルゴリズム（確率的でも決定的でもいいですが）って、
素数表を必要としないのが特徴ですが、
素数列挙の場合は自然数Nが素数か調べるときにN未満までの素数表が使えます。

これって生かせるんでしょうかね……。それが良くわからない。
生かせないとしたら、このスレの存在価値は無しなんですが。
生かせるとしたら、エラトステネスを超えるアルゴリズムはあるんでしょうか。

>>126
URL見るだけでエラトステネスだってわかるけど

>>130
1度作ってみると分かりますよ。
素数表を保持する性質上、メモリの無駄を抑えるところで差がつくんです。

>>40を改造した2,3飛ばし。間違っててもノークレームで頼む。

extern "C"{
　　int printf(const char*,...);
　　long atoi(const char*);
　　void *calloc(size_t num, size_t size);
　　void free(void *memblock);
}

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

　　if(1<c){
　　　　m=atoi(v[1]);
　　　　if(1<m){
　　　　　　printf("2\n");
　　　　　　if(2<m){
　　　　　　　　printf("3\n");
　　　　　　　　if(3<m){
　　　　　　　　　　if((m&1)==0)
　　　　　　　　　　　　m--;
　　　　　　　　　　n=(m-3)>>1;
　　　　　　　　　　P=(char *)calloc(n+1,sizeof(char));
　　　　　　　　　　P[n+1]=1;

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

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

あ、一箇所インデント狂った

>>1-133
ほんとオマエらヴァカばっかだな。
オレが最速のソース伝授してやるよ。
今回は1桁のみ出力するソースだけど、
少ない脳みそ使って大きな値にも対応しろ。

#include <stdio.h>

void main(void)
{
　　int primes[]=
　　{
　　　　2,3,5,7
　　};
　　int ii;

　　for(ii=0; ii<sizeof(primes)/sizeof(primes[0]); ++ii)
　　{
　　　　printf("%d, ", primes[ii]);
　　}
}

素数生成多項式ならずううーーーーと前からあったよ。

>>135 それが何か関係あるの？

#include <stdio.h>

void main(void)
{
　　int primes[]=
　　{
　　　　2,3,5,7,11
　　};
　　int ii;

　　for(ii=0; ii<sizeof(primes)/sizeof(primes[0]); ++ii)
　　{
　　　　printf("%d, ", primes[ii]);
　　}
}

漏れって>>134より頭いい。

>>134も>>137も、>>68で概出なのよ

http://pc3.2ch.net/test/read.cgi/tech/983191866/910-911
でも外出

begin 644 prime2.cpp.gz
M'XL("&*<9ST"`W!R:6UE,BYC<'``A53;CMHP$'U.OF)81!66RT(?N56H6JV0
M%HJZ4E6)(A02`U:-@Q*'O53\>\<7'`>HR@OQV'/FS#EC5RF/6!X3&&0BIDE[
M-_*K;HC1=3DFZ)[(B%^-R89R`M/);#(=3U?S[Y/I(WRV\>?)[/%E-1W_A&Y'
M_GP_8F&6P3Q%A&=YXH]_R->,1CW?6R<)@Y1D.1-]W\MY1K><Q,`2O@7*!1QD
MTLV=*$]3PF46Y4RB6OP`HH1G`JYSPA\ARPG4D8'G*6@8FB#B>`;2QF`P@"YN
MG'S?>WA`FB)/.1S5U@)$BG]+V).0XVH?OH-68FD9J>:B'8E^_YO2T6&D=<#R
[email protected]=!-`Q4@%=0Q8NHVAE<DS'*VB)__4+QGP1#A)0Y&DTH64'D-!>HZ\
MDI+DGJTR^B$1K:KW.KYP_%W>-`9KB;GF4_CL>F0I!+KMHAZVWI%=6`@,E,>L
M90TQB,>$QC".8VV\PY:3UV+B="$IH5,,]2UZ48J:#HLSC08Z/"QAE<LKB[]Q
M\B+((?B/O<ZL(Z8<']GK=0[%W9('WNN.,NR.MEHP@H[F:H`^F;,+NH36Z#QM
MINSMB2AK]S5DT8R\:;W/CISU;S3Z@)-_2),M`F2%MR`25.5-%.0JA0S%J;K1
MU<'#M;4+=76O;2E/%=XD.8^+8XK]Y4Q="_A$1*`^N+U82@,.`]?_+T8YKI33
MST%/#>`MC<J(IND.(G)T175YH:2]?3)O'U*N$<)T&S71IS"]E]_'Q5)#7MS.
M0VFI7CD!\@W.Y/.$&#@)76P!=VF@@;H2J8>O+IZ6)U<"UF1+.29$+,&QD)3*
MN&W=F<8UVUQL@KM:+'9:<T2LL1C6[U"+%PHG6_[B=TW9L<IK7G!M*_DU)%Y7
8J#?/Y7&I"<E*QA,D>_+_`@?NRDV-!@``
`
end


小さい方から1万個程度の列挙で80秒くらいかかります。
( PPC G4 400MHz, MacOS X 10.1 )

せっかくかいたので、ageちゃいます。

/*
140です。
なんか、うまく展開できなさっぽいので、分割してみます。
全部くっつけてコンパイルしてみて下さいませ。
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MINIMAM_PRIME 2
#define LINES_MAX 100000

class PrimeLine {
public:
bool result;
unsigned long int prime;
unsigned long int current;
inline PrimeLine( const unsigned long int aValue ) {
prime = aValue;
current = aValue << 1;
}

// return value [ true ] mean [ may PRIME ]
inline bool check( const unsigned long int value ) {
result = value != current;
if( ! result )
current += prime;
return result;
}
};

// I'm 140 ....
class PrimeGenerator {
private:
unsigned int lines_size;
PrimeLine* lines[ LINES_MAX ];
unsigned long int lastPrime;

public:
inline PrimeGenerator() {
lines_size = 0;
lastPrime = MINIMAM_PRIME - 1;
}

inline void AddLine( PrimeLine* newPrimeLine ) {
if( lines_size != LINES_MAX )
lines[ lines_size++ ] = newPrimeLine;
}

inline bool OneStep( unsigned long int value ) {
bool result = true;
unsigned long int i = lines_size;
while( i-- > 0 )
result &= lines[i] -> check( value );
return result;
}

inline void CalcNextPrime() {
lastPrime++; // progress lastPrime to next
while( ! OneStep( lastPrime ) )
lastPrime++;
AddLine( new PrimeLine( lastPrime ) ); // found new Prime
}

public:
inline unsigned long int Get( int n ) {
return n < lines_size ? lines[n] -> prime : 0;
}

inline void Calc( int n ) {
while( 0 < n-- )
CalcNextPrime();
}
};

// 140です。
// メインです。なくていい？
int main( int argc, char* argv[] ) {
PrimeGenerator primeGenerator;
int times = argc > 1 ? atoi( argv[1] ) : 10;
time_t begin = clock();
primeGenerator.Calc( times );
printf("%dth Prime : %ld by %d[clocks]\n",
times, primeGenerator.Get( times - 1 ), clock() - begin );
return 0;
}

ぐぐれば終わりだろが。
http://gt.sakura.ne.jp/~nyagy/integer/sosuu_seisei.html

>>144
ﾜﾛﾀ。

５
やったぜ、素数見つけた

素数10000個列挙に20秒、
60000個列挙に12分。
これってどう？全然戦えてない？

>>147 dame
Vectorあたりで何個か落としてみろ

>>147
10000個目、60000個目の素数が何だか知らんが
1000000までの素数を列挙する（ちなみに素数の数は78498個）のに
400MHzのCPUで0.75秒。

Vector内では恐らくこれが最速。
http://www.vector.co.jp/soft/win95/edu/se221945.html

急浮上

#!/usr/local/bin/ruby
# >>141
MINIMAM_PRIME = 2
LINES_MAX    = 10000

class PrimeLine
    attr_accessor :result
    attr_accessor :prime
    attr_accessor :current

    def initialize( aValue )
        @prime = aValue
        @current = aValue << 1
    end

    # return value [ true ] mean [ may PRIME ]
    def check( value )
        @result = value != @current
        if ( ! @result )
            @current += @prime
        end
        return @result
    end
end

# >>142
class PrimeGenerator
private
def initialize
@lines = Array.new( LINES_MAX )

@lines_size = 0
@lastPrime = MINIMAM_PRIME - 1
end

def addLine( newPrimeLine )
if( @lines_size != LINES_MAX )
@lines[ @lines_size+=1 ] = newPrimeLine
end
end

def oneStep( value )
result = true
@lines_size.downto(1) do |i|
result &= @lines[i].check( value )
end
return result
end

def calcNextPrime
@lastPrime += 1 # progress lastPrime to next
while ( ! oneStep( @lastPrime ) )
@lastPrime += 1
end
addLine( PrimeLine.new( @lastPrime ) ) # found new Prime
end

public
def get( n )
return (n < @lines_size) ? (@lines[n].prime) : 0
end

def calc( n )
n.times do
calcNextPrime
end
end

def enum
result = []
@lines.each do |o|
next if o.nil?
if o.result
result << o.prime
end
end
return result
end
end

# >>142 retry (sorry!!)
class PrimeGenerator
    private
    def initialize
        @lines = Array.new( LINES_MAX )

        @lines_size = 0
        @lastPrime = MINIMAM_PRIME - 1
    end

    def addLine( newPrimeLine )
        if( @lines_size != LINES_MAX )
            @lines[ @lines_size+=1 ] = newPrimeLine
        end
    end

    def oneStep( value )
        result = true
        @lines_size.downto(1) do |i|
            result &= @lines[i].check( value )
        end
        return result
    end

    def calcNextPrime
        @lastPrime += 1 # progress lastPrime to next
        while ( ! oneStep( @lastPrime ) )
            @lastPrime += 1
        end
        addLine( PrimeLine.new( @lastPrime ) ) # found new Prime
    end

    public
    def get( n )
        return (n < @lines_size) ? (@lines[n].prime) : 0
    end

    def calc( n )
        n.times do
            calcNextPrime
        end
    end

    def enum
        result = []
        @lines.each do |o|
            next if o.nil?
            if o.result
                result << o.prime
            end
        end
        return result
    end
end

# >>143
if __FILE__ == $0
primeGenerator = PrimeGenerator.new
times = (ARGV.empty?) ? 10 : ARGV[0].to_i
t_begin = Time.now
primeGenerator.calc( times )
puts primeGenerator.enum.join( " " )
printf("%dth Prime : %d by %d[clocks]\n",
times, primeGenerator.get( times - 1 ), Time.now - t_begin )
end

# ふう。。。Rubyに移植してみたのれす。。
# でも・・・・・遅いっすね★

>>◆DhJkQxJw
俺はRubyのコトはよく分からんのだが過去レスに色々ソースがあるから
見てみ（大概Cだけど）。

がんがれやヽ( ´ー｀)丿

･ﾟ･(ﾉД`)･ﾟ･ｳﾜｰﾝ
漏れの活躍してた素数スレが消えちゃったよ〜★

1 ：移転したよ。。。 ：移転
移転しました。。。
こちらです。http://pc3.2ch.net/pc3tr/

↑ここ逝っても何もないしさぁ・・・。

>>157
しばらくすると消えるから必要なレスをコピペして。
http://pc3.2ch.net/test/read.cgi/pc3tr/1030500162/

正直、どこをどう読めば活躍してるのか分からない。
頑張って勉強していたスレ、というなら認めるが。
活躍というなら、>>126を超えてくれ。

>>158
うひひ☆サンクスれす☆

>>159
ごめそね★
「暗躍」って言い換えればいいれすか？

ちなみに、漏れが自力で作った最速コードは
これ↓れした。いかな厨房でも理解できそうれす。

#!/usr/local/bin/ruby
hajime = 2
saidai = 100

hajime.upto(saidai) { |i|
    flag = true
    next if ((i != 2) && (i % 2) == 0)
    3.step(i-1, 2) { |j|
        break if (j ** 2) > i
        if (i % j) == 0
            flag = false
            break
        end
    }
    print i, ", " if flag
}

これでも>>152-155よりは早いのれす。
求めた素数をすべて配列に保持するアルゴリズムを
実装すると、かえって速度が落ちるようなのれす。
うひひ。

>>160
無駄レスするな。暗躍の意味をわかっているのか小一時間。

>>152より上を見るのがかったるくなってしまったが>>150は速いな…

昨晩は>>116のコードをRubyに移植しようと
がんがっていたのれすが、ポインタに対して
ビット演算してたりして、お手上げれした。
これから>>126を移植すべく、アサヒ スーパー
ドライを含んだ頭でせいぜいがんがります。
よろしく☆

こんな奴が俺より年上なのか、情けない。

かすみ遊戯のかすみみたいな口調虫唾が走る。

>>164
うひひ★どうせ漏れはﾄﾞｷｭｿれすよ★
ﾄﾞｷｭｿはﾄﾞｷｭｿらしくしてるのが
一番なのれすよ★
ﾊｧｧ･･･

>>165
お前が酒を飲むなんぞ10年早いわ。
だいたい >>126 のruby版は既にあるし。

>>166
20歳だから飲んでもいいんだもん★
つーか「かすみ遊戯」って何？
って思ってぐぐるしたら、エロゲじゃん。
げろげろげろー

＞だいたい >>126 のruby版は既にあるし。

なんてこったい★漏れとしたことが★

で、計ってみました★
（ただしこれまで同様printはコメントアウト）

$ time ./esieve4.rb 100000
Prime numbers such that p<=100000 are,

real 0m0.149s
user 0m0.140s
sys 0m0.015s

・・・・・・試合放棄してもいいれすか？

>>167 試合放棄？
そうか、ここまでよく頑張ったな。いいよ。

･ﾟ･(ﾉД`)･ﾟ･ｳﾜｰﾝ
いぢめっこがいるよ〜★

　　　　　　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　　　　　　｜も.｜
　　　　　　　　　　　　　　　　　｜う　|
　　　　　　　　　　　　　　　　　│来│
　　　　　　　　　　　　　　　　　│ね│
　　　　　　　　　　　　　　　　　│え .|
　　　　　　　　　　　　　　　　　│よ .|
　　　　　　ﾊﾞｶ　　　　ｺﾞﾙｧ　　│ !!.│
　　　　　　　　　　　　　　　　　└─┤　　　　ﾌﾟﾝﾌﾟﾝ
　　　　ヽ(`Д´)ﾉ　ヽ(`Д´)ﾉ　　(`Д´)ﾉ　　　 （　`Д）
　　　　|￣￣￣|─|￣￣￣|─|￣￣￣|─□（ ヽ┐U
〜 〜　￣◎￣　　.￣◎￣　　￣◎￣　　 ◎−>┘◎

はじめまして〜☆
こんばんわ〜☆

さっそくですけど、>>150ってすごいれすね。
10億まで計算しても>>161の10万より早いとは。
Uvaで参戦しようと思ったのれすが、もうだめぽ・・・★

面白くない。

保守

>>172
ていうか、sageてない？

>>173
sageのまま保守することがいけないことか？

>>174
禿同！！

保守はsageでするべきだと思う。

>>175
そういいながらageて書く君が好きだ

ちょっとでも速いアルゴリズムを書きたいが小手先の技になりそうだな…

>>176
やってみれば。
小手先の技でも塵も積もれば山となる…かも

そうだな

そうれすね

俺付属の脳ｺﾝを使うと
A>list　素数
1、2、3，5、7、11、13、17、19、23、26、29、31、37とでてくる。
A>

>>180
馬鹿31は素数じゃねぇよ

>>181
馬鹿はあんただよ…

おばかさん１は素数じゃねぇよ

と言ってみたかったと無理やり弁護してみるテスト。

8　*　9＝31
は　　く　さい
白菜

めっちゃ素直にふるいを実装。
% time ./era 10000000 78497
prime[78497] is 999983
3.560u 0.390s 0:04.16 94.9% 0+0k 0+0io 0pf+0w
G４450Mhz でこのくらい。
「./era」がバイナリ。
最初の引数が、ふるいの大きさ。
次の引数で、いくつめの素数を表示するかを指定( チェック用 )

アイデアがあるので、これから改造。

>>185 頑張ってくれ。俺はこれといった面白いアイデアが無い。

ところで、999983 は78498番目の素数だと思う。
０からカウントをしているということか？
「いくつめ」という時は普通１からだよ

>>185
改造したらソースきぼ〜ん☆

ソースがいっぱい

ttp://lecture.ecc.u-tokyo.ac.jp/~kuno/cp01/report/report2b.html

>>188
数はあるけど…

まぁ、プログラミングの練習の段階ですから

"直感的な素数の倍数を飛ばす[ふるい]”を実装してみました。
% time ./sieve 10000000 5
prime[664578] -> 9999991
1.940u 0.400s 0:02.55 91.7% 0+0k 0+0io 0pf+0w ( G4 450MHz )
ちょっとだけ、早くなりました。
ちなみに、最初の引数がふるいの大きさ。
二つ目の引数が、"直感的な素数"の最大値。
なぜか、5のときが、最速でした。
# この値を大きくすると、どんどん早くなるはずだったんだけどな。

ソース upしたいけど、253行にもなっちゃった。

あぷろだにうｐ！

数が大きくなればなるほど素数の出現頻度は低くなるの？

>>191
凄く厨な事聞いてるみたいで恥ずかしいのだが、
＞1.940u 0.400s 0:02.55 91.7% 0+0k 0+0io 0pf+0w ( G4 450MHz )
これの読み方がわからぬ(；´Д`)
何が何を表してるのか教えてくだされ。。

http://tool-ya.ddo.jp/2ch/trash-box/contents.jsp?file=20020801121545017.zip
あ、遅刻だ...

>>193
π(x)〜x/log(x)なんだそうな。
だからちょっとずつ頻度は低くなる。

>>195
ファイルが見つかりません…

http://tool-ya.ddo.jp/2ch/trash-box/file/20020913081215032.gz
これはどなた？

>>198
それです！指摘サンクス！
なんで間違っちゃったんだろう....遅刻までして....
あー。死にたいなぁ。


ちなみに、up直前に、偶数だけはチェックしないようにしたところ、

% time ./sieve 10000000 5
prime[664578] -> 9999991
1.720u 0.380s 0:02.46 85.3% 0+0k 0+0io 0pf+0w

位まで改善されました。
ちなみに、この出力の見方はよく分かりません。
0:02.46 って部分が、2秒46っぽいので、
この部分が短くなるように努力してます。

200 get!っと

>>185さん 俺 C++知らないんだけど、
このプログラム class いっぱい使ってるよね。

これくらいのプログラムなら main にダラダラ書いてもいいんじゃない？
可読性は下がるけど、速度面では有利だと思う

>>200
っていうか、漏れｱﾌｫなので、
一個のメソッドが30行くらいを越えると、
全然理解できなくなっちゃうのです。

誰かmainにまとめたバージョンうｐきぼんぬ

age

>>202
七行スレに依頼しる！

>>204
見づらさが500％増加の見込み

出入りの激しいループの奥深くの関数以外は速度面から見てもベタ書き不要。
コンパイラによってはinline指定子もあるし。

まだレジスタの出入りの心配をした方がましかと・・・・・・。

>>206 正論だな

素数なんて列挙してどうするの？

>>201
30行？カスだな。

>>208 より速く、より高く、より遠くへ。男のロマソだ。

>>210 同意
シンプルな問題ではあるが、奥が深い
素数自体がおもしろい数だし

>>208
賞金もらえるぞ

そこに素数が（可算個）あるからだ。

hoshu

限界目指してます

ほっしゅ

列挙ってことは、配列かなんかに
素数を全部入れなきゃ駄目？

>>217 標準出力とかに順番にヌケも間違いも無く出せればそれでいいと思うよ。

>>217
速さを目指すなら、バイナリでファイルに出力することを推奨

最後は可読な状態で出力がいいな。
バイナリだと何でもありになりそうだから…

>>220
出力0.0001秒、表示200時間とか？

んなのがあるかい

>>220
そうだな。
じゃあテキストで、tab 又は 改行で区切るってことで。

個人的には , で区切るのはやってほしくない。
言語によっては、ファイルを読む処理がめんどくなる

素数なんか列挙して何になるの？

全然プログラミングと関係無いねえじゃん。
数学板帰れよアホ。

>>224
禿しく慨出。

>>224
数学は列挙したりなどしない。定義さえすれば、そこにあるものだから。
そして利用する場合には、プログラム的なアクセスが必要になる。

板違い。

数学とプログラム、特にアルゴリズムは深い関係があるのを知らないのかい

素数列挙列挙ではあんまり数学的なテクニックが使えないからねえ。

素数列挙って言うと、
1:エラトステネスの篩
2:順番に素数判定
の二つしか知らないのだけど、もっと素敵な列挙法ってないでしょうか？

>>230
素数データベースから読み出して表示
（列挙は列挙でしょ♪）

enumerate of prime numbers.

適当な奇数を表示して問いかける。

>>233
意味が良くわかんないんだけど。
説明していただけるかしら？

>>234

21 は素数ですか?)(y/n) _n
21 は素数ではありません。
13 は素数ですか?(y/n) _y
13 は素数です。
（以下同じ）

それは、>>230の2に該当ということでいいのか

結局エラトステネスが一番素敵だと思う。
プラス2の倍数を飛ばしてみたり。

上のほうに2と3の倍数を飛ばすのがあったけどそれ以上のはめんどくさそうだね…

>>237
「2の倍数」って・・・。


以前受けた突っ込みを他人にしてみるテスト。

>>237 胴衣

あとは早い言語で、良い実装をする。これに尽きる

あと如何にメモリの使用量を抑えるかですな

数学板より
http://science.2ch.net/test/read.cgi/math/1033486518/
http://science.2ch.net/test/read.cgi/math/1030077269/

>>237
無限に存在する素数を相手にする時に限界があるよね。
2の倍数、3の倍数の枝刈りのようなもの。

>>242
俺たちにゃ有限の時間しか残されていないのだから、有限でいいのさ

ピタゴラス数を列挙(・∀・)ｼﾖｰﾖ
a²+b²=c²な数を！

[{3,4},{5}]

bracket brace three comma four brace comma brace five brace bracket

>>244
それセンター試験でやった。懐かすぃ

素数列挙。篩ばかりがもてはやされているが、
敢えて isPrime系を選択してみた。
isPrimeには、平方根を求める操作が必須だ。
「sqrtのアルゴリズムは知らないが、
　そんなに軽くないんじゃないの？」
そんな直感が、僕にこのコードを書かせた。

>>248
どのコードよ？

書き込もうと思ったが、長過ぎたようだった。

#ifndef PrimeEnumerator_included
#define PrimeEnumerator_included
#include "RootEnumerator.h"
typedef unsigned int prime_t;
class PrimeEnumerator {
protected:
    prime_t  prime_max, prime_count, current, root, divider, i;
    prime_t* prime_list;
    RootEnumerator rooter;
    inline bool CurrentIsPrime() {
        root = rooter.Next();
        for( i=0; i<prime_count && ( divider=prime_list[i] ) <= root; i++ )
            if( current % divider == 0 )
                return false;
        return true;
    }
public:
    PrimeEnumerator( prime_t new_max );
    ~PrimeEnumerator();
    void Calc(); 
    inline prime_t Get( prime_t i ) {
        return i < prime_count ? prime_list[i] : 0;
    }
    inline prime_t GetCount() {
        return prime_count;
    }
};
#endif
このファイルは、 PrimeEnumerator.h という名前で。

#include "PrimeEnumerator.h"

PrimeEnumerator::PrimeEnumerator( prime_t new_max ) {
    prime_count = 0;
    prime_list = new prime_t[ prime_max = new_max ];
    rooter.SetFirst(2);
}
PrimeEnumerator::~PrimeEnumerator() {
    delete[] prime_list;
}
void PrimeEnumerator::Calc() {
    for( current = 2; current < prime_max; current++ )
        if( CurrentIsPrime() )
            prime_list[ prime_count++ ] = current;
}
#include <stdio.h>
#include <stdlib.h>
int main( int argc, char* argv[] ) {    
    unsigned int i = 1 < argc ? atoi(argv[1]) : 10000;
    PrimeEnumerator primeEnum( i );
    primeEnum.Calc();
    unsigned int count = primeEnum.GetCount();
    printf( "%dth prime -> %d\n", count, primeEnum.Get( count-1 ) );
}
これは、 PrimeEnumerator.cpp 。

#ifndef RootEnumerator_included
#define RootEnumerator_included
#include <math.h>

class RootEnumerator {
protected:
    int number, root, limit;
    inline void SetLimit() {
        limit = ( root + 1 ) * ( root + 1 );
    }
public:
    inline RootEnumerator() {
        number = limit = root = 0;
    }
    inline void SetFirst( int i ) {
        root = (int)sqrt( number = i );
        SetLimit();
    }
    inline int Next() {
        if( limit < ++number ) {
            root++;
            SetLimit();
        }
        return root;
    }
};
#endif
これが、平方根を連続的に求めるためのコード。
RootEnumerator.h という名前で。

性能は、このくらい。

% time ./primer 10000000
% 664579th prime -> 9999991
% 22.540u 0.180s 0:25.17 90.2% 0+0k 0+4io 0pf+0w

CPU PowerPC G4 450MHz
OS  MacOS X 10.2
c++ コマンドに -O3 オプションをつけて、コンパイルした。

このプログラムの rooter.Next() という記述を、
(int)sqrt( current ) に変更して実行してみると、
10000000までの素数の計算に、 3秒ほどよけいにかかるようになる。
30行ものコードを追加して、3/10000000 秒程度の
高速化しかなされていない。

今後 2や3の倍数をのぞいて計算できるようにもしようかと思ったが、
ばかばかしくなってしまった。

>>248-255をRubyに移植してみた。

$ time ./primer.rb 10000
1229th prime -> 9973

real 0m0.395s
user 0m0.296s
sys 0m0.062s

$ time ./primer.rb 100000
9592th prime -> 99991

real 0m5.773s
user 0m5.171s
sys 0m0.046s

1000000になると数十秒待っても終わらなかった。

どっちばれ。

全部を一ファイルにまとめている。

#!/usr/local/bin/ruby

class PrimeEnumerator
protected
def CurrentIsPrime
@root = @rooter.Next
0.upto(@prime_count-1) do |i|
break unless ( (@divider=@prime_list[i]) <= @root )
return false if( (@current % @divider) == 0 )
end
return true
end

>>257はボツ。やり直し。

>>248-255をRubyに移植してみた。
全部を一ファイルにまとめている。

#!/usr/local/bin/ruby

class PrimeEnumerator
protected
    def CurrentIsPrime
        @root = @rooter.Next
        0.upto(@prime_count-1) do |i|
            break unless ( (@divider=@prime_list[i]) <= @root )
            return false if( (@current % @divider) == 0 )
        end
        return true
    end

public
    def initialize( new_max );
        @rooter = RootEnumerator.new
        @prime_count = 0
        @prime_list = Array.new( @prime_max = new_max, 0 )
        @rooter.SetFirst(2)
    end
    def Calc
        2.upto(@prime_max-1) do |current|
            @current = current
            if( self.CurrentIsPrime )
                @prime_list[ @prime_count ] = @current
                @prime_count += 1
            end
        end
    end
    def Get( i )
        return (i < @prime_count) ? @prime_list[i] : 0
    end
    def GetCount
        return @prime_count
    end
end

class RootEnumerator
protected
    def SetLimit
        @limit = ( @root + 1 ) * ( @root + 1 )
    end
public
    def initialize
        @number = @limit = @root = 0
    end
    def SetFirst( i )
        @root = Integer(Math.sqrt( @number = i ))
        self.SetLimit
    end
    def Next()
        if( @limit < (@number+=1) )
            @root+=1
            self.SetLimit
        end
        return @root
    end
end

if __FILE__ == $0
    i = (0 < ARGV.length) ? ARGV[0].to_i : 10000
    primeEnum = PrimeEnumerator.new( i )
    primeEnum.Calc
    count = primeEnum.GetCount
    printf( "%dth prime -> %d\n", count, primeEnum.Get( count-1 ) )
end

>>256
実行環境を教えて下さいませ。

>>262
Windows 2000 Pro SP3 + Cygwin 1.3.12 + ruby 1.6.7

AMD Athlon XP 2100+ (1.73GHz), RAM 512MB

UD, Winny, Mozilla, かちゅ〜しゃ常駐　です。

結局エラトステネスしかないってわけか。

ただし、同じ環境でもc++では早かったから
Rubyが遅いだけ、と思いねぇ。

$ c++ PrimeEnumerator.cpp -O3 -o primer

$ time ./primer 10000
1229th prime -> 9973
real 0m0.045s
user 0m0.046s
sys 0m0.030s

$ time ./primer 100000
9592th prime -> 99991
real 0m0.077s
user 0m0.062s
sys 0m0.030s

$ time ./primer 1000000
78498th prime -> 999983
real 0m0.645s
user 0m0.609s
sys 0m0.015s

$ time ./primer 10000000
664579th prime -> 9999991
real 0m13.577s
user 0m12.156s
sys 0m0.061s

C++を素直にRubyにしたコードよりも、
もっとRubyらしくした方が、高速になりませんか？

「数学のたのしみ」という雑誌の２８号に素数のおもしろい話がのってたよん
ちと高いが

すごいよ

#include <stdio.h>

#define MAX_NUM 100

int main(void){
int i;
int j;
int count;

for (i = 2; i <= MAX_NUM; i++){

count = 0;

for (j = 1; j <= i; j++){
if (i % j != 0){
count++;
}
}

if (count == i - 2){
printf("%d\n", i);
}

}
return 0;
}

何がじゃ

>>268
30点。
正常に素数を列挙することに精いっぱいで
高速化のための工夫がまるでありませんね。
ただ、どんな本やお勉強サイトにも
こんなコードは載ってないでしょうから、
>>268さん自身が自力で書いたコードであることが解ります。
この点は、評価に値します。

今後は、以下の点に注意してがんばってみましょう。
「数が素数かどうかを調べるための % 演算の回数を
  できるだけ少なくする。」

期待していますよ。

ところで、数学のこと全然知らないDQNなんだけどさぁ、

　　n(1) = 2
　　n(2) = 3
　　n(3) = 5
　　n(4) = 7

こういうのを満たす関数って見つかってるの？

最高100までとかの制限はもちろんありだけど
最高どこらへんまで有効な式が見つかってるのかなあ。

>>267
引用してよぅ。すごい興味あります...

>>271
関数の形で素数を表現するだけでしたら、
集合 {y | gcd(1,y)=1, y!=1} に順序を与えればよいってことで。

{y|IsPrime(y)=true}

>>273
うーみゅ。数学に詳しくないからあれなんだけど、
ある程度の数まで有効な素数ジェネレータがないか
ってことなのれす。。。

昔どっかの掲示板で、
「任意の有限の数列を表現する 一般的な方法」
をみた気がする。

ﾊｧﾊｧ･･･うーみゅ･･･(；´Д｀)
ﾊｧﾊｧ･･･ｴﾄﾗｽﾃﾈｽ!(・∀・)

>>277

>277
不安になってググッちまったよ。
残念ながら、エトラステネスでは一件もヒットしなかった。

>>275

その関数はある･･･からこそ計算機で計算もできる。
有無じゃなくて、計算にかかる時間が問題になってるわけです。

>>279
エストラテネスなら2件ヒットしたぞ。

>>280
>>275が欲しがっているのはシーケンシャルな計算なしで、
一発で( O(1)で )素数を求めるための式でしょ。


アルゴリズム的な方法をとるのなら、
int prime( int i ) {
    static const int p[100] = { 2, 3, 5, 7, 11 , ... };
    return p[i];
}
みたいな関数作っておけばいいだけなんだけども。
数学的な数式となると...数学板で聞いた方が早いかな。

>>272
http://www.nippyo.co.jp/maga_suutano/st28.htm
ｽﾏﾝ　立ち読みで済ませてしまった。１６００円もするから。
内容は、素数のいろいろな定義の仕方から始まって、
素数の数え上げ、素数の間隔、双子素数など。
ページ数もかなりさいてある。図書館にあればコピーしたいなぁ

>>282
たとえば
　(A)　n + 1
ならnが1から2までなら成り立つっしょ？

こんな感じの簡単な数式が欲しいのれすが、
どうもスレ違いな予感。。。

メルセンヌ何とかやらとか…
確かものすごい次数の式になった気が。

つかそんなんあるんだったらとっくに出てると思う。


＃「そんなん」で「成男」出たよ。なんじゃこりゃ

>>285
いや、だから100までとか1000までとかの間に
限って成り立つ式なら簡単な数式でも
ありそうなものだと思ったわけでつ。。。

自分で作れば？
100までの素数を解にもつ多項式なら作れるじゃん。
たとえば10までだったら
(x-2)(x-3)(x-5)(x-7)=0
これが>>286がほしい方程式じゃん。

ごめん、関数と方程式間違えた。。。

でも関数なら
f(x)=ax^3+bx^2+cx+d
と置いて、
f(1)=2,f(2)=3,f(3)=5,f(4)=7
を解けば未知数4個で式も4つだから10以下の素数求められるんじゃん？
同じように力技で100だろうが1000だろうがいけると思う。
素数がわかってなきゃ解けないから意味ないけど。

っていうかラグランジュ補間とかニュートン補間でいけるか。
何度も書き込みすまそ。

超すごいよ

#include <stdio.h>
#include <math.h>
#define MAX_NUM 100000

double sqrt(double x);

int main(void){
int i;
int j;
int count;

for (i = 2; i <= MAX_NUM; i++){

count = 0;

for (j = 1; (double)j <= sqrt((double)i); j++){
if (i % j != 0){
count++;
}
}

if ((((double)count <= sqrt((double)i) - 1 ) &&
(sqrt((double)i) - 1) < (double)count + 1)){
printf("%d\n", i);
}

}
return 0;
}

成長があまり見られん

while(0){
fprintf(stdout,"計算中です！！（止めないで）");
fprintf(stderr,"（次の素数をお願いします…（こそーり））");
scanf(&x);
fprintf("あ？次の素数？%dに決まってんだろボケ",x);
}

素数列挙してよし。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1035246186
　　　　　　　　　　　 ＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧　 　　／
　　 ミ,,ﾟДﾟ彡　＜　　書いてみたです。
　　 ,;ﾞ　　 ﾐ　 　 　＼　
　＠ﾐ,,,UUﾐ　　　　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　ｴｽﾄﾗの2の倍数/3の倍数を使ってみますた。
　　　　　　　そんなに高速化できませぬですた。

>>294
だから、ｴｽﾄﾗとかかかないでよ！
どれが正解だか解んなくなるしさ！

>>291
40点。
だからさ、countが2になったらループ続ける意味ねーだろ。

　ミ,,ﾟДﾟﾐつ...反応が、、、、ニャイ、、、、だれかコードのあれとか、、、
　　　　　　　　　　　　　　　　　　　　　コメントないの？

>>296
１億 or １０億 or 2^31 or 2^32 以下の素数を求めるのにかかかる時間と実行環境ｵｾｰﾃ

>>296
すまん。つーか、コード長過ぎて、見る気がせん。
のんきな人だったら、週末まで待ってくれ。

あと、計算時間と実行環境は知りたいなぁ。
Delphi なんて持ってないし、ってゆか漏れマカーだし。

　　　　　　　　　　　 ＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧　 　　／
　　 ミ,,ﾟДﾟ彡　＜　　すごく遅いはずよ。
　　 ,;ﾞ　　 ﾐ　 　 　＼　
　＠ﾐ,,,UUﾐ　　　　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣
ﾋﾞｯﾄごとで素数か否かを判断して
2の倍数と3の倍数を削除してるだけだから。
ドノーマルのフルイです
メモリ使用量は少ないので.
容量が必要でオチるのはないと思うですが

あとはどうやって高速化するんですか？

･･･いや、激しく外出だとは思われなんですが・・・

　∫,,,,,,,,,∧,,∧　 　300ｹﾞﾄ
⊂,,,,,,,,,つ,,ﾟДﾟﾐつ
　　　　　　　　このｽﾚ、、住人少ないの？

６ヶ月でレスが３００というのは、少ない方だろう

　∫,,,,,,,,,∧,,∧　 　3日経っても
⊂,,,,,,,,,つ,,ﾟДﾟﾐつ Int32.Maxまでの素数は
　　　　　　　　　　　求まっていなかった,,,もしかしたら300日くらいかかる？

>>302 ガンガレ

こっちに書きます。
＞どうせなら　3*5*7*11*13 のテーブルを用意してリピートして使えば
＞17から開始出来ます。

　３と５の倍数にマークをつけた表は 3*5=15ワード毎に繰返します
　3,5,7,11,13の倍数全部にマークを付けた表は同じく全部の積のワード毎に繰返します。
　ですから、最初に倍数全部にマークを付けたそのサイズの表を作って、それをMove関
　数を使ってコピーし、
　最後に 3.5.7,11,13の所のマークを消せば　初期化が出来る訳です。


＞あと、2個ペアでループを回すのも速くなります
　同じワードを読んで書く場合、キャッシュが効きます。キャッシュが効けば、２度目のアクセスは
　ほぼ無いのと同じです。
　特に小さな数の間に大きな効果があります。
　たとえば 17 19 をペアにして x,yの小さい方に xなら17 yなら19を足すようにすると、
　コードは増えますが、その実行サイクルはメモリアクセスに完全に隠れてしまいます

チラっと見たけど TBitsを使っていますね？
TBitsを使うなら、最初にそのサイズを取得しておく方がいいです
また、この命令中に分岐が入っているので、遅い場合もあります。

偶数を無視して書き込む場合

var tbl:array of byte;

procedure SetBit(n:Cardinal);
var bit,adr:Integer;
begin
bit:=1 shl((n and $F) shr 1);
adr:= n shr 4;
tbl[adr]:=tbl[adr] or bit;
end;

procedure ResetBit(n:Cardinal);
var bit,adr:Integer;
begin
bit:=1 shl((n and $F) shr 1);
adr:= n shr 4;
tbl[adr]:=tbl[adr] and (not bit);
end;

function TestIsPrime(n:Cardinal):boolean;
begin
Result:=((n and 1)<>0)and ((tbl[n shr 4] and (1 shl((n and $F) shr 1)))=0);
end;

なお、TestIsPrimeの中で偶数ならfalseを返していますが
速度を考えるならホントはループ中に入れない方がいいです。
偶数でも値が2の時はTrueを返すとかの処理も

ただ、SetBitに比べると頻度はずっと小さいので
Test関数が遅くても　それほど遅くはならないですが

　　　　　　　　　　　　 ＿＿＿＿＿＿＿＿＿＿＿
　　　 ∧,,∧ 　　　 ／
　　　ミ,,ﾟДﾟ彡　＜ 　さんくすこですー
　　　ﾐ　つ日　　　＼＿＿＿＿＿＿＿＿＿＿＿
　.＠ﾐ,,,,,,　,,ﾐ
>それをMove関数を使ってコピーし、
理論は理解しました。
でも。その初期化処理を具体的に
どう実装するのかがわからんですの。

TBitsとかTBooleanDynaArrayとかTListとかだと
ＩｔｅｍやBitsをＭｏｖｅで初期化するのって
どうやるのでしょうか。

そもそも、全てをＴｒｕｅにするのも、すごい初歩的な
やり方しかしてないので、その辺りのメモリ操作を
教えてください。>>304

>　たとえば 17 19 をペアにして x,yの小さい方に xなら17 yなら19を足すようにすると、
>　コードは増えますが、その実行サイクルはメモリアクセスに完全に隠れてしまいます
ごめんなさい。理解できません。偽コードで示していただければ
わかるかもなのですが...

と、書いてから305以降をﾊｹﾝしますた。読んでみます。

詳しい説明ありが�d

procedure eliminateDual(n,m:Cardinal);//n,mは$ffff以下である事
var x,y,n2,m2:Cardinal;
var i:Integer;
var bit,adr:Integer;
var tim:DWORD;
begin
write('ふるう数=',n,',',m);
tim:=GetTickCount;
n2:=2*n; m2:=2*m;
x :=n*n; y :=m*m;
while　(x<y) do begin
　　SetBit(x);
　　x:=x+n2;
　 end;
while　(x>n2)and(y>m2) do　begin
　 for i:=1 to m do begin
　　SetBit(x);
　　x:=x+n2;
　 end;
　 for i:=1 to n do begin
　　if y<m2 then break;
　　SetBit(y);
　　y:=y+m2;
　 end;
　end;
writeln('　かかった時間=',GetTickCount-tim);
end;


ふるう数=17　かかった時間=3315
ふるう数=19　かかった時間=3155
ふるう数=17,19　かかった時間=3986

上のコードは、
最初に似た値に近づけておいて 2*n*mの同じブロックサイズで検索するというものです
n,mが多くなると効果が出ませんが、n,mが大きくなればどうせ同じメモリバスを指す確率も減るので
n,m<200程度で使うと良いでしょう。
完全に隠れるという訳にはいかないけど、効果のある節約です
もっと多重にすればもっと効果が上がりそうですが、条件判断を増やさないでやるのは難しいです。

と色々書いたけど、実際にはこういう事をやっても1分でも計算時間を短くするのは難しいです。

普通に書けば32bitのふるいはメモリが300Mあるマシンなら10分もかからないで完成する筈ですから

２の倍数だけでなく３の倍数を表から除くテクニックを利用する場合、
nの倍数を埋める場合、6で割った余りが 1と5の時だけ埋めれば良いので
n2:=2*n n4:=4*nと用意しておいて、交互に足します


７の倍数を埋める場合 初期値x=7*7=49 6で割った余りは１なので 49を埋めた後次は x:=x+n4 その次はx:=x+n2とループします

忘れていました。
　2,3の倍数を表から除いた場合、
セットすべきビット位置は x div 3 で　求まります。

コードとしてはこんな感じです。 TBits.Bits[] を使って

n:=5;
while n< SQRTMAX do begin
if not Bits[n div 3] then begin
　 writeln(n,' ',GetTickCount-t0);
　 x:=(n*n) div 3;
　 n2:=2*n;
　 n1:=(n div 6)*4+3;
　 while x<MAX3 do begin Bits[x]:=True;Bits[x+n1]:=True;inc(x,n2);end;
end;
inc(n,2);
if not Bits[n div 3] then begin
　 writeln(n,' ',GetTickCount-t0);
　 x:=(n*n) div 3;
　 n2:=2*n;
　 n1:=(n div 6)*8+1;
　 while x<MAX3 do begin Bits[x]:=True;Bits[x+n1]:=True;inc(x,n2);end;
　 end;
　 inc(n,4);
end;
コード中の　while x<MAX 　の停止条件が甘いので、BitsのSizeは(MAX+SQRTMAX)/3にしておいた方がいいです

>>312
function TPrimeListTBitsTripleOverCompress.AccessInsideIndex(
　OutSideIndex: Integer): Integer;
begin
　Result := ((OutSideIndex div 6)*2)
　　　　　　+
　　　　　　((OutSideIndex mod 6) div 5);
end;
こんな感じだと思ってたのですが、
これって、x div 3 なのでしょうか？

|,,∧　　･　・　・　・　
|Дﾟ彡
|　U
|　ﾐ 　　　
| U

>>314 >>313のコードを見て下さい。 nには 6で割った余りが1と5しか来ないようになっていますね？
最初に5 2を足して7 4を足して 11 2を足して13 というふうに回るからです。

そこで n=6*k+1 と n=6*k+5 と書きます

すると、n div 3 は 2*k か 2*k+1になりますね？

|,,∧　　ｱﾗﾔﾀﾞ すごいわぁ
|Дﾟ彡
|　U
|　ﾐ 　　

>>314
除算は整数でも浮動小数点ユニットが使われたりで、並列演算が出来ないから
そういうふうに連続して使わない方がいいよ。　合計３つも連続して使うとストールする。

|,,∧　　　素数列を文字列でｽﾍﾟｰｽ区切りしたらMaxInt32で
|Дﾟ彡 ファイルにして、1ｷﾞｶﾞになちゃう勢いなんですが
|⊂ﾐ 　…
|　ﾐ 　　　Webにウプする場所がない…
|''U そもそも、俺の56K回線では…

誰かCに翻訳してくれ…意味がわからん｡･ﾟ･（ﾉД`）･ﾟ･｡

>>318 そんなもの計算させる前に見積もりさせないとさあ

フルイの状態が一番効率がいいんだよ。だからフルイのままで持っておいて問合せに対して
出力させたら？　でも100MもRAM取ると鯖屋に嫌われるか

とだけ書くと、単なる煽りなので
0〜N を１０進で改行付で列挙する場合のおよその必要バイト数
　
N*(log10(N)+2)/loge(N)
l

>>319
どのコードを？

>>322
>>305,308,313
つまり全部…

int TestBits(unsigned char *tbl,unsigned int bit)
{ return tbl[bit>>3] & (1 << (bit &7));
}
void SetBit(unsigned char *tbl,unsigned int bit)
{　tbl[bit>>3] |= (1 << (bit &7));
}
unsigned char * MakePrime32bit( void )
{
const MAX3=0x55555555;
unsigned char * tbl = malloc(0x20010000/3);
unsigned int n=5;
　memset(tbl,0,0x20010000/3);

　while (n<0x10000){
　　if(! TestBits(tbl, n / 3) ){
　　　unsigned x =(n*n)/ 3;
　　　unsigned n2= 2*n　　;
　　　unsigned n1=(n/6)*4+3;　printf("%5d\n",n);
　　　while( x<MAX3){SetBit(tbl,x);SetBit(tbl,x+n1);x+=n2;}
　　}n+=2;
　　if(! TestBits(tbl, n / 3) ){
　　　unsigned x =(n*n)/ 3;
　　　unsigned n2= 2*n　　;
　　　unsigned n1=(n/6)*8+1;　printf("%5d\n",n);
　　　while( x<MAX3){SetBit(tbl,x);SetBit(tbl,x+n1);x+=n2;}
　　}n+=4;
　}

　return tbl;
}

int isPrime( unsigned char *tbl,unsigned n)
{ switch(n%6){
　 case 0: return 0;
　 case 1: return !TestBits(tbl,n/3);
　 case 2: return n=2;
　 case 3: return n=3;
　 case 4: return 0;
　 case 5: return !TestBits(tbl,n/3);
　}
}

ありゃ　こうか
int isPrime( unsigned char *tbl,unsigned n)
{ switch(n%6){
　 case 1: return !TestBits(tbl,n/3);
　 case 2: return n==2;
　 case 3: return n==3;
　 case 5: return !TestBits(tbl,n/3);
　}
　return 0;
}

で，テストプログラム
int main(int argc, char* argv[])
{ unsigned char *tbl= MakePrime32bit(　);
　int n=29999900,i;
　 while(1){
scanf("%d",&n);
　　for(i=0;i<10;i++){
　　　　while(!isPrime(tbl,n))n++;
　　　　printf("%8d\n",n++);
　　}
　}
　free(tbl);
return 0;
}
29999903
29999923
29999927
29999941
29999947
29999989
29999999
30000001
30000023
30000037

>>304
どこから来たの？どのような概念？

>>324〜
どのようなことを考慮したプログラムなの？

ゴメン、詳細キボン

324は >>313をcで書いたものです。

　ただし TBitsは無いので SetBits/TestBitsの関数に置き換えました。

それと、0〜0xFFFFFFFF の範囲の列挙ができるようにしています。
マシンに256M以下のメモリしか無い人は実行すると異常に遅くなるでしょう。

>>304 の件は >>310 の通り、実施してもビックリする程早くはなりません。
>>324 のようなテクニックの方が確実に早くなると思います

わざわざ詳細な解説有難うございます。
感謝します。

n1:=(n div 6)*4+3 のようなマジックナンバーが疑問なのかな？

nは (6*k+1) か (6*k+5) k=0,1,2...　と表現出来ます。

xは (6*k+1)*(6*k+1)/3,(6*k+1)*(6*k+5)/3,(6*k+1)*(6*(k+1)+1)/3,(6*k+1)*(6*(k+1)+5)/3,...
のようになります。
後は差分を求めれば解決します。

差分を求めて、処理を高速にするテクニックは　デジタル微分解析法 (DDA)です。

これは基本的に身に付けておくべきテクニックの一つです。

更に混乱した

確かに>>.324は速いね。　最速かな？

>>333
そんなに速いの？　バイナリupｷﾎﾞﾝ

>>334
GCCでもBCCでもコンパイル出来るだろ

>>334
フサギコのコードより倍のサイズを列挙してるのに、３桁以上速い

具体的にどのくらい早いの？

たぶん２千倍くらいじゃない？　想像だけど

エラトステネス 対 除算なら千倍ちかく差がでるのは分かってたけど
エラトステネス同士でも実装次第で千倍くらい変わるんだ　へぇ

　ミ,,ﾟДﾟ彡　
私も自分のコードを1000倍くらい高速化したですよ。

高速化よりも消費メモリが少ないほうが重要そうですね
Int32MaxIntまではがんがっても70MB程度は必要なのかな。
一昔前のものなら動かないし

Int64最大値までの素数値列を出すのはかなり遠いですね。

>>340
まずInt32MaxIntって書くより　2^31-1　って書いてくれた方が判り易いよ

サイズについては、2,3,5を除けば あと５M小さく出来るよ。
コードは大きくなるし、速度の効果は2割だから書きたくないけどね。

2^63-1の素数列を列挙するのは、世界中のHDを集めても容量が足りないでしょう

やるとすれば、2^64-1で指定された場所から 2^31個のフルイを作る事でしょうね

　　　　　　　　　　　 ＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧　 　　／
　　 ミ,,ﾟДﾟ彡　＜　　さらさらっとそういう計算できるのって
　　 ,;ﾞ　　 ﾐ　 　 　＼　なかなか頭の切れがよいですね。
　＠ﾐ,,,UUﾐ　　　　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣
2^31-1 = 2147483647
2^63-1 = 9223372036854775807

2147483647ビットのフルイの箱が必要で
圧縮して1/3とかもうちょっとだけが減らせるから
8で割ってバイト数を出し
3で割って圧縮かけるということで
89478485.291≒90MB

同様に計算すると
9223372036854775807のフルイに必要なのは
384307168.ギガバイトですかね。
オンメモリで用意できるのはずっと先ですか...

>>342
例の定理が正しいとすれば
50年先ですから、生きてる間に見える可能性は高いかな・・・いや、CPU速度が追いつくのはさらに倍か

6ヶ月でレスが300というのは、少ない方だろう

だーかーらー。
http://pc3.2ch.net/test/read.cgi/tech/983191866/910-911
が最速なんだってば。

>>345
とりあえず１０億まで計算させてみろ！　話はそれからだ

>>345
(0〜2^31) という条件だと、難しいんでは？

132番目の素数はもう出たの？

>>348

2^743-1　は素数ではありません

std::pow(2, 743)-1

4.62686e+223

(・∀・)?

46268644699475435470014199270680622913148582491776246164412857235254375716637876222457838321585848270371190628323884999935972095850551557285913445801770125007762163162852820919462003875720454598226040577701224945512200798207

なんで224桁もあやふやにならずに書けんだよ！
と問いたい。おっぱいを突付きながら問い詰めたい。

UBASICを使えば簡単

ところで、132番目の素数って何のこと？
メルセンヌ素数は 40番目くらいを探索中でしょ

>>352
俺にも突っつかせろ

>>353
「132番目の素数さん」は数学板のデフォルトの名無しさん。
132番目の素数が743（名無しさん）であることから。

浮上

　　　　　　　　　　　　　　　 ＿＿＿＿＿
　　　　　 ∧,,∧＿__　　 ／
　　　 ／ミﾟДﾟ,,ミ／＼＜　　とりあえずupッときまつた
　　／|￣∪∪￣|＼／　＼＿＿＿＿＿
　　　 |＿＿＿＿|／

http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1035246186&res=10
これ動かしたら、10時間後には
0〜int32最大までの素数列
ｽﾍﾟｰｽ区切りで数値の書いたテキストファイル
1GB分があなたの手元に！

ところで、Vectorにあるような素数列挙ソフトと比べるとどう？
素数xpとか。

そりゃ全然かなわないよ。
1兆も計算出来るという事は 37bitの計算が出来るわけだし。

こんな方法はどうだろ？
上で出てる２，３の倍数を除く手法を拡張して、N迄のすべての素数の倍数を除くコードを
吐き出すプログラムを作るというのは

>>359
>>113が近い？

OO さいこー!!

　　　　　　　　　　　 ＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧ 　　　／
　 _ ミ,,ﾟДﾟ彡 _＜　unsinedint最大まで求めるってのは
.=| |=U===U=| |= ＼いいかもしんない
　| | .ﾐ　 　ﾐ　| | 　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣
　| |ﾉ∪''∪.　| | しかし…もう篩いの容量が
　　　　　　　　　劇的には減らないですねー

1兆は2^34では？
でも、私の試算ではメモリが715MB弱ほどは必要？！
どうやってんでしょ...

2^34 = 171 7986 9184

171億 7986万 では？

　　　　　　　　　　　　＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　 ∧,,∧ 　　　／
　 _　ミ,,　　彡_＜　　ゲーム脳で頭が腐ったみたいです。
.=| |=ﾐ 　　ミ=| |= ＼
　| | ﾐ＠　ミ　| | 　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣
　| |　∪''∪　| | 鬱だ。
　| |　　　　　 | |
　　　　　　　　　　

2^32 -1 迄のは >>324で出るようだが？

篩の結果を 算術圧縮したらどうなるんだろ？
圧縮する時の係数を　n bit目を 1/log(n)　としたら、ほぼ完全な乱数になるのだろうか？

おいデルフサー
てめーああん？


カワイイじゃねえか、乳揉むぞｺﾙｧ

>>362
一気に計算する必要はないんよ。
過去ログにそういうアルゴリズムがあった。

>>362
Del使ってないからわからんのだがunsinedintってなに？
unsignedintの親戚かなにかか？

>>369
もう★　そんな野暮なこと聞くなんて
おちゃめさんなんだからぁ♪

　　　　　 　 　　　　∫　　　 ＿＿＿＿＿＿＿＿＿
　　　∧,,∧ 　　 　∬　　 ／
　　 ミ,,゜Д゜彡っ━~　　＜　安心Edintを知りませんか？
＿と~,,　　~,,,ﾉ_. 　∀　　　＼　
　　　 ﾐ,,,,/~), │　┷┳━ 　￣￣￣￣￣￣￣￣￣
￣￣￣ .じ'Ｊ￣￣|　┃
￣￣￣￣￣￣￣ 　┻

　　　　　　　∫　　　 　　　　 ＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧ ∬　　　　　　 ／
　　 ミ,,-Д-ノ,っ━~　　＜　・・・ 俺も知らない・・・
＿と~,,,　　~,,,ﾉ＿.　∀　　 ＼
　　　 .ﾐ,,,/~),　　.|　┷┳━ 　￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣ .し'J￣￣|...　┃
￣￣￣￣￣￣￣ 　 .┻
>>368
使わない所の古いはＨＤに退避させとくのですか？
速度とかの辛味で難しそうですね。

>>126　のソースコードの作者だけど、Delﾌｻｷﾞｺ さんのソース良さげな感じ。
そのうちアイディア取り入れさせて貰います。

>>371
エラトステネスの篩いにおいて、ある数Nが合成数かどうか知るためには
√Nまでの素数リストがあれば十分です。

逆に言えば2からMまでを篩った結果（小素数表）があれば、それを用いて
M+1からM^2までを篩うことができます（拡張素数表）。

そして、拡張素数表の部分は一度に篩う必要はないです。任意サイズに
分割することができます。

ただし、

1. 分割すると、各分割の先頭でoffsetを定めるための除算が必要になるので
　 分割しすぎると除算のコストが高くなる。

2. 分割が少なすぎると、一度に篩うべき領域が大きくなるので、キャッシュが有効に
　　働かず、メモリーアクセスのコストが高くなる。
　　最悪の場合、swapが頻発してHDにアクセスしてしまうかもしれない。

という条件を考えて適切な分割サイズを定める必要があります。
これはマシンの一次,二次キャッシュのサイズにも依存しますし、微妙なところです。
とりあえず256KBあたりが無難な線ですが、多分最適サイズは他にあります。

分割された各領域の先頭でoffsetを定めるところだけ64bit演算を導入すれば、
32bitマシンでもあまり代わったことをしないで32bitMAXより上を篩うことも可能です


# ……最近某所で、キャッシュを有効にするための凄まじい方法も聞きました。

>>372
あのリンク貼った者です。まさか降臨なされるとは。

　　　すごいっす。
　　　　 .Λ,,Λ. 　＿＿_ 　
　　　　ミ；ﾟДﾟﾐ　.||::::::::||
　　 　ミ　　 つ___||_____||　
　　　|￣￣|__ﾐ―――――
　　　`ー┬‐''
　　　　　┴
>エラトステネスの篩いにおいて、ある数Nが合成数かどうか知るためには
>√Nまでの素数リストがあれば十分です。

ゲーム脳なので、具体的な数値でしかも小さい数で
話しないと、何のことがわからなくなってしまうので書いておきます。

100=10^2前後の値で
97/89/83は素数、101 103 107 109 113 も素数
√97=9以上...10未満→9.(?)
97が素数だと判定する為には
1〜9.(?)までの素数列(つまり[ 2 3 5 7 ])
これで割り切れるかどうかを調べたらいい.
ってことでしたよね。

82,84,85,86,87,88,90,91,92,93,94,95,96,98,99
100,102,104,105,106,108,110,111,112,114,115,116,117,118,119,120
は全部、[ 2 3 5 7 ]のどれかで割り切れると。いうわけっすね。

でも、それはあくまで
ある数(この場合97とか)が素数かどうかを調べるために
篩いを使う方法なわけで、

結局、97が素数って判定した後は
それをどこかメモリに貯めておかなければならないのかな？？？
いや、、求めた瞬間にファイル出力したらいいのか...

　　　　　わけわかなくなってきた。
　　　　 .Λ,,Λ. 　＿＿_ 　
　　　　ミ　　,,彡 .||::::::::||
　　 　ミ　　 つ___||_____||　
　　　|￣￣|__ﾐ―――――
　　　`ー┬‐''
　　　　　┴
私のコードは2147483647までの
素数篩いはメモリ上に構築可能なので(90MBもあるけど)
それを利用して
2147483647*2147483647=
4611686014132420609
までの値が素数かどうかはわりと、はやく判定できるのかな。

…それでもInt64の最大値　(2^63)-1　=
9223372036854775807
には届かないわけっすね。

それにしても、2147483647〜4611686014132420609までは
一つ一つの値に対して、素数篩いに問い合わせなければいけないので
相当遅いことになる予感しま・・・・・

いや、そうじゃなかったですか。

> 逆に言えば2からMまでを篩った結果（小素数表）があれば、それを用いて
> M+1からM^2までを篩うことができます（拡張素数表）。
> そして、拡張素数表の部分は一度に篩う必要はないです。任意サイズに
> 分割することができます。
　　　　　
　　　　 .Λ,,Λ. 　＿＿_ 　また勘違いから
　　　　ミ　　,,彡 .||::::::::||　　遅いコードを書くはめになりそうなオカンでした
　　 　ミ　　 つ___||_____||　
　　　|￣￣|__ﾐ――――― 上のカキコみて。ちょっとわかた。よかた。
　　　`ー┬‐''
　　　　　┴
1〜2147483647の素数篩い(基本篩い)を利用して
例えば2147483647〜(2147483647*2)の篩い(拡張篩い)を用意して
(メモリ上は90MBふたつになるわけで)
基本篩いで求まる素数列で拡張篩いを振るってしまえばいいってことですね。
んでもって、拡張篩いを次に(2147483647*2)〜(2147483647*3)あたりで
用意して、また篩うと…いうわけっすね。

なんかすごいことになっていきますね。

なんか、ここにも謎な誤爆が,,,
Kylixってどこで使われてるの？
http://pc3.2ch.net/test/read.cgi/tech/1032182284/l50
の52

2,3,だけじゃなくて、5,7,11も抜きたいけど,,,
いったい、どうやるんだろかしら、、、、まだまだ奥深いです。

落ち着け。

どうも言葉が足りなかったようで、分かりにくくてすみません。
>>376で仰ってる通りの感じです。

Rubyなんで読みにくいかも知れませんが、一応そのあたりのことが
http://idm.s9.xrea.com/factorization/eratosthenes.html
に書いてあります。

# この文も直さなきゃなー。
# 「3,5,7の倍数を除いても無駄」とか書いてあるし。
# 昔、試したところでは確かにあまり効果が上がらなかったんだけれど、
# このスレ見てる限りではどうも私の実装が腐ってただけみたい。

　　　　　　　　　　　 ＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　∧,,∧　 　　／　試行錯誤したり
　　 ミ,,ﾟДﾟ彡　＜　　実装したりして、いろいろ
　　 ,;ﾞ　　 ﾐ　 　 　＼　わかってくるものっすね。
　＠ﾐ,,,UUﾐ　　　　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣

1-100で、Excelで手動でふつってみてわかったですが
リンク先の所に書いてあるメモリ消費の問題

バカ正直に1-100の入れ物を用意した場合を100として
篩の箱を
2の倍数消したら当然残りが50箱でメモリ消費半分50%
3の倍数消したら残り2/3でそれを2の倍数ので割ってメモリ消費1/3　33%
5の倍数消したら(4/5)*(2/3)*(1/2)=(4/15)=26....%
7の倍数消したら(6/7)*(4/5)*(2/3)*(1/2)=(8/35)=22....%
11の倍数消したら(10/11)*(6/7)*(4/5)*(2/3)*(1/2)=(16/77)=20.7....%

くらいの効率っすか。11まで事前に圧縮かけていても270MBの１/５程度にしか
ならないから、int32最大までの素数を求める篩は
55MB程度のメモリは必要っすね。

2,3,5倍数消ししたクラス2,3,5,7を消したクラスを作成して
比較してみたのですが
メモリ消費量は減りますが
計算速度は高速化してないようでした。

>>379
高速化するなら　>>324のようにしなくちゃね。
0〜(2*3*5*7*11-1) で１と 2.3.5.7.11以外の素数のある個所を除いたテーブルを用意して
それを篩のビットを消す時に使うようにする。

　　　　　　　　　　　　2/3/5/7消しで高速化したら
　　　　　∧,,∧ 　　　　High(Cardinal)な素数ﾌﾙｲが
　　　　 ミ,,ﾟДﾟ彡 　＜ 30分程度で計算できるように
　　　　　ミ　つ且~~ 　　なったのですが、
　　　　　ﾐ,,__　ヾ
　⊂二二二UU二二⊃ それをIntToStrすると、
座して待ちすぎ？　　　2GBのテキストファイルになって
　　　　　　　　　　　　　　それをファイルに生成するとこで
　　　　　　　　　　　　　　30時間程かかりました。

最後はこんなんであってるかな？
4294966997 4294967029 4294967087 4294967111 4294967143
4294967161 4294967189 4294967197 4294967231 4294967279 4294967291

あってるみたいだね。おめでとう。
しかし30時間もかかるもんなのか…

保守っとく

　　,,,,,,,,,,,,,∧,,∧　　 ／IntToStrで普通に数値を文字列変換して
〜′,,,,,,,ミ,,ﾟДﾟ彡＜　追加ってるから、めちゃ遅くなってるですね。
　 UU""" U U　　　＼
　　　　　　　　その辺りを高速化する気にはならなかったです。

なんか、D7からIntToStrがｱｾﾝﾌﾞﾗになったとかならないとか。
TBitsのﾒﾓﾘｲﾒｰｼﾞをﾊﾞｲﾅﾘファイルで保存できたら
面白いかもしれません。
(それでも数十MBのファイルはあまり扱いたくないかな。)　　　　　　

、、以下２をのぞて
・２の倍数は素数ではない、つまり素数は奇数でなければならない
・素数（奇数）と素数（奇数）を足すと素数ではなくなる
・素数の１以上の倍数は素数ではない　eg: 13*2=26 13*3=39->39/3=13

素数の２乗を６で割った余りは必ず１である

なんてね。>>385はうまいネタでも思いついた？

50000までの素数を求めるプログラムをCで組んでくれませんか? おながいします

ごめん、日本語の読めない厨房をここへ誘導してしまいました
回線切って、首釣ってきます．．．

>387よ、おまえにお似合いのプログラムを書いてやった
早くこのプログラムを提出しろ。

#include <stdio.h>
#include <math.h>

void main()
{
　　double i, j, flag;

　　for (i=2;i <= 100;i++)
　　{
　　　flag = 0;
　　　for (j=2;j < i;j++)
　　　　if ((i/j)==floor(i/j))
　　　　　flag = -1;

　　　if (flag==0)
　　　　printf("%lf\n", i);
　　}
}

ありがとぅございました

セミコロン1つくらい省略しておけばよかったのに･･．

厨は逝けや

>>392
ｵﾏｴｶﾞﾅｰ

define(`genprime',`ifelse($#,1,`genprime(2,1,$1)',
  `ifelse($1,$3,`(total decr($2))',`ifelse(chkprime(1,$1,$2),1,
      `$1 define(`prime$2',$1)genprime(incr($1),incr($2),$3)',
      `genprime(incr($1),$2,$3)')')')')dnl
define(`chkprime',`ifelse($1,$3,1,`ifelse(
  expr($2%prime$1),0,0,`chkprime(incr($1),$2,$3)')')')dnl
genprime(1000)

高速化&圧縮
define(`era',`ifelse($1,$2,`(total $3)',`ifdef(`sym$1',`era(incr($1),$2,$3)',
`$1 fill(eval(`$1*2'),$2,$1)era(incr($1),$2,incr($3))')')')define(`fill',
`ifelse(eval(`$1<$2'),1,`define(`sym$1',)fill(eval(`$1+$3'),$2,$3)')')define(
`primes',`era(2,$1,0)')primes(10000)

2^32-1までの素数をファイルに出力するのに、
AthlonXP 1800 メモリ 512MB で 2分50秒くらい
Pentium2 400MHz メモリ 128MB で 14分くらい
ってどうですか？

>>396
健闘してるんじゃない？　>>150といい勝負かも

ファイル出力込みの時間はディスクの状態によって結構変わる
測定前にデフラグをかけるとよろし

>>397
FreeBSDだからデフラグは関係無いみたいです。
あと、150とは全然比較になりません。
そもそも多倍長整数が扱えませんし。
多倍長整数ってすごく難しそうなイメージがあります。

>>394-395
なんだこりゃ?

最速ﾊｹｰﾝ！
http://www.crt.or.jp/~kokochi/sosu.htm

＞MMX Pentium 150 MHz のパソコンで、 0 ≦ 整数値 ≦ 4,294,967,295
＞の全素数 203,280,221個をカウントするのに、約 16 分を要する。

うえーんPrologで自己展開形式素数計算プログラムキボン( ●Д●)

>>400
天進法かよ！

>>400
それは知っているよ。

小さい方からの素数の最少公倍数ごとに区切っていくものでしょ。

少＝＞小
なんでこんなバ化なんだ家の辞書（バ化だって・・・ＴOＴ）

>>400を使った場合、
この前発表された公式と、どう比べたら良いのか、詳細希望。

>>406
「この前発表された公式」と言うのはインド人が見つけたアルゴリズムのこと？

>>407
そうかもしれない。あっちは素数一つを求める事が出来るとかか？

[列挙]が付いているからな、
このスレタイには

判定のほうは随分前にdat落ちしたからね

改良した結果、2^32-1までの素数を計算するのに(正確には203280221番目の素数を計算するのに)
AtholonXP 1800 で 40秒台
Pentium2 400MHz で 3分30秒台
まで縮まりました。ファイル出力は無しです。

>>411
ファイル出力ありの記録希望

ファイルシステムが違うので、比較不能と思われ

もうちょっと改良したところ、ファイル出力なしだと、
Athlon で 35秒、
Pentium2 で 3分20秒、
ファイル出力ありだと、
Athlon で 2分ちょうど、
Pentium2 で 9分ちょうど
ぐらいでした。

途中で、関数は全部マクロで書いたほうが速いことに気付いたのですが、
ファイル出力関連はめんどくさくて直してなかったので遅いです。
あと、n を p で割った答を a ,余りを r に代入するのに、
r = n - (a = n / p) * p;
とかしてたんですけど、普通に
a = n / p; r = n % p;
と並べたほうが速い(ほとんど変わらないけど)ことに気付きました。
コンパイラが最適化してくれるのでしょうか。
アセンブラを知らないので、内部的なことがよく分かりません。

ソースきぼん

>>415
除算命令は余りも同時に求めてくれるから、そのせいだと思います。
aを計算した段階で、rの値もレジスタに入ってるので。

でも、コンパイラがそこまで最適化してくれるんだ……。コンパイラは何ですか？
前にgcc 2.95で試したときはご丁寧に除算してくれてたけど。

私もソースきぼん。

× ご丁寧に除算してくれてたけど。
○ ご丁寧に二回除算してくれてたけど。

http://tool-ya.ddo.jp/2ch/trash-box/file/20021126122038042.c
人に見られることを意識していないので、死ぬほど汚たないです。
変数名一文字とか、変数使い回しとかいっぱいあります。
そのままだとファイル出力しないので、print_integerのコメントアウトを
二箇所はずしてください。fopenなのであらかじめprime.datというファイル
がないといけないかもしれません。ファイルは2G超えるので注意して下さい。

>>417
そうなんですか。レジスタとかよく分からないけど。
コンパイラは gcc 2.95.3 です。-O3をつけてます。

VCだとコンパイルできないのね

1億まで（ファイル出力あり）
>>324　52秒
>>419　50秒
K6-2 400MHz

324の 0x20010000 はどこからきてるんだろう。
(n/6)*4+3 は (n*2-1)/3
(n/6)*8+1 は (n*4-1)/3
でもいいですね。

ほんとは
0x20000000+0x10000/8　でいいのかな？
余裕を取っただけでは？

unsigned char * MakePrime32bit( void )
{
const MAX3=0x55555555;
unsigned char * tbl = malloc(0x20010000/3);
unsigned int n=5,m=1,n1,n2, d;
memset(tbl,0,0x20010000/3);
n1=3,n2=10,d=8;

while (n<0x10000){
if(!TestBits(tbl, m) ){
unsigned x = d;
printf("%5d\n",n);
while( x<MAX3){SetBit(tbl, x);SetBit(tbl, x+n1); x += n2;}
}n1+=2*m+4 /*(n*2+8)/3*/,n2+=4,d+=4*m+4 /*(n*4+4)/3*/,n+=2,m++;

if(!TestBits(tbl, m) ){
unsigned x = d;
printf("%5d\n",n);
while( x<MAX3){SetBit(tbl,x);SetBit(tbl,x+n1);x+=n2;}
}n1-=2*m-2 /*(n*2-8)/3*/,n2+=8,d+=8*m+8 /*(8*n+16)/3*/,n+=4,m++;
}

return tbl;
}

計算量を減したはずが、逆に遅くなりました。
なんでなんだろう。
あと、ここのプログラムはどうなんでしょう。
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

>>425は毎回 n1,n2類の計算をしてるけど>>324は素数の時だけしてるからでは？

高速にするなら
１、SetBit　を展開して高速にする
２、２つの倍数消しを順にではなく交互にする >>308

unsigned char * MakePrime32bit( void )
{
const MAX3=0x55555555;
unsigned char * tbl = malloc(0x20010000/3);
unsigned int n=5,m=1,n1,n2, x;
memset(tbl,0,0x20010000/3);

while (/*n<0x10000*/ m < 21845){
if(!TestBits(tbl, m) ){
/* n == 3 * m + 2 */
x = m*(3*m+4)+1;
n2 = 6*m+4;
n1 = 2*m+1;
printf("%5d\n", 3*m+2);
while( x<MAX3){SetBit(tbl, x);SetBit(tbl, x+n1); x += n2;}
} m++;
if(!TestBits(tbl, m) ){
/* n == 3 * m + 1 */
x = m*(3*m+2);
n2 = 6*m+2;
n1 = 4*m+1;
printf("%5d\n", 3*m+1);
while( x<MAX3){SetBit(tbl,x);SetBit(tbl,x+n1);x+=n2;}
} m++;
}

return tbl;
}

>>427
確かにそうですね。でも428でも遅いんですけど、なんか間違ってるかなあ。

単純に、アライメントが変わったからじゃないの？１割２割は命令の配置番地で変わってしまうよ。

参戦♪
と言う訳で32以下の素数と、それ以上の素数を分けて篩いました
gcc2.95 オプション -O でコンパイルして K6-233(←CPU遅すぎ) で
2^32-1 までの素数を数えるのに4分弱でした

↓はそのソースです
無意味に構造体を使ってるので読みづらいですが…

http://tool-ya.ddo.jp/2ch/trash-box/file/20021129234010029.tgz

アスロン1700+で1億まで求めたら24分かかった・・・
（ ﾟдﾟ）ﾎﾟｶｰﾝ

改良しても7分半かかった・・・
（ ﾟдﾟ）ﾎﾟｶｶｰﾝ

ただいま作成中･･･。

>>432
main()の
for ( n = 1 ; n < 65536 ; n += 1 ) {}
nの値を1億に変えてませんか？
分かり辛いですが、このままで 2^32-1 までを求めてます

>>432
直接１億にしたら、もっと時間が掛かりそうですね…
取りあえず、各値を変えないで、実行してみてください

>>431
すいませんその時間は私が自分で作ったヤツのです(ウン子すぎ）。
（６n±1　を sqrt(6n±1)までの素数でひたすら割るもの）
2^32-1 までで4分っすか・・・早いですね。

畜生・・・VBで組んで、10万までは3秒、100万までは1分29秒・・・。
100万まで1秒切れるというのはマジすか？？？

>>438
最適化のオプションをいじくるとか

VB最強ってことか・・。

>>438
ここVB製。
http://f1.aaacafe.ne.jp/~zxrg/

419から5の倍数も除いたもので、
AthlonXP 1800 で 20秒
Pentium2 400MHz で 2分11秒
ぐらいでした。

改良して10万なら2秒。100万までなら43秒・・・（VBで）。
>>441のものには全然敵わない・・・くそ！！！

>>443
もしかして除算型のアルゴリズム使ってない？
エラテネシのほうが早いよ。

エラテネシって何すか？
検索したけれども・・・ない。

>>445
エラトステネス

　 （　・∀・）　　　|　|　ｶﾞｯ
　と　　　　）　 　 |　|
　　 Ｙ　/ノ　　　 人
　　　 /　）　 　 < 　>__Λ∩
　 ＿/し'　／／. Ｖ｀Д´）/ ←>>444
　（＿フ彡　　　　　 　　/

1億まで求めるのに3分45秒まで短縮できたけどもうだめっぽい。
次はエラテネシでやってみようかのぅ・・・

保守

これやるとエラーが出る・・・。
ちなみに100000だと計算してくれる

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
int i,j,k,l,m;
int p[1000001];
ofstream fout;
m=0;
l=1000000;
k=int(sqrt(l));
fout.open("素数.txt");
for(i=2;i<=l;i++){
p[i]=1;
}
for(i=2;i<=k;i++){
for(j=2*i;j<=l;j++){
if(j%i==0){
p[j]=0;
}
}
}
//続く

//続き
for(i=2;i<=k;i++){
for(j=2*i;j<=l;j++){
if(j%i==0){
p[j]=0;
}
}
}
for(i=2;i<=l;i++){
if(p[i]==1){
fout << i << '\n';
m=m+1;
}
}
cout << "素数は全部で" << m << "個です" << '\n';
fout.close();
return 0;
}

>>451は間違い。こっちだった。
//続き
for(i=2;i<=l;i++){
if(p[i]==1){
fout << i << '\n';
m=m+1;
}
}
cout << "素数は全部で" << m << "個です" << '\n';
fout.close();
return 0;
}

これは遅いですか？

#include <stdio.h>
int main()
{
int i,j,k;
for(i=2; i<100000000; i+=(i==2)?(1):(2))
{
i+=(i%3)?(0):(2);
for(j=2; (double)j<sqrt((double)i); j+=(j==2)?(1):(2))
{
if(!(k=(i%j))) break;
}
if(k){
printf("%d\n",i);
}
}
scanf("\n");
return 0;
}

>>453
除算型の中でも遅い方だと思う。

>>453
Cのコンパイラ持っていないので分かりません。
どれぐらい時間かかった？

2、3日かかりそうで怖いな

知ってたらすまそ〜ん。
今日会社で仕事中に思いついたいい方法を書くよ〜ヒントだけど。
（ちなみにオイラはこの方法でしこたま短縮した）

１．「整数乗余」演算子を使わない（C/C++なら％、VBならMod）
２．エラストテネスのふるいをやる。

この方法でしこたま速くなる！！！

>>457
しこたま速くなるんじゃなくてしこたま遅かったんだろ。お前のが。

全然進歩しないね
これが２ｃｈの限界

>>458
そうだよ。
>>459
お前に言われたくない。

エラトステネス以上のアルゴリズム、誰か知らない？

>>457
>１．「整数乗余」演算子を使わない（C/C++なら％、VBならMod）
%ではなく　/ を使えということ？

>>457
このスレを最初から読むことを勧める。
>>461
あったらいいなぁと思う今日この頃。

下記のプログラムは素数を出力するのですが､
本当に素数が出力しているのか自信がありません。
どなたか試していただけませんか？
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000
int main(void)
{
int s[] = {2, 3, 5, 7};
int ss[MAX] = {0};
ss[0] = 1;
ss[1] = 1;
for(int i = 0; i < 4; i++){
int n = s[i] + s[i];
for(int j = 0; n < MAX; j++){
if(ss[j] != 1){
ss[n] = 1;
n = n + s[i];
}
}
}
for(i = 0; i < MAX; i++){
if(ss[i] != 1){
printf("%10d", i);
}
}
printf("\n");
return 0;
}

素数って上限の有無はまだ確定してないですよね？

>>465 無限にあることが証明されている。

なるほど。
つーことはリストに照らし合わせる必要がある限り、
無限のメモリが必要か。

エラトステネスで解こうとする場合、次の素数がどのくらいか予想できないと
どれほどのリソースが必要か分からない。

予想はできてるんですか？

そんなこと考えるよりさ
漏れたちでエラトステネスより
オーダの小さいのアルゴリズムを
考え出せばいいのさ

>>467
勉強の為に作っただけなので、とりあえず１万桁でいいです。

そいやどこかに、今のスパコンでどのくらいかかるか出ていたっけ。
ってことは、おおよそ見当はついているのか。

力業が通じるかどうかってことなんだ。

素数の判定に他の素数との割り算を必要としないアルゴリズム？

>>471
だから、割り算をすると遅くなるんだよ。
発想の転換をしようや。

エラトステネスのどこに割り算を使うんだ？

>>472
このスレ全部読めよ

>>473
任意のn〜mまでの素数を列挙する時じゃねえか？

>>475
フルイを作っていけば勝手に出来るだろ

俺の現況：
VBでテキストファイルに入力しない場合は
100万以内の素数を調べるのに平均0.7秒台
テキストファイルに入力すると平均1.1秒台。

VC++（MFCを使わない）の場合は、
上のVB同じ条件で、ファイルに入力しないと平均0.2秒台
ファイルに入力すると2.2秒台・・・あれれ？？？

>>441のVB製に勝ててないが、俺は2の倍数を初めから除いていない。
ちゃ〜んと2の倍数を消すところから計算スタートしてるの。

いま分かっている最大の素数。約405万桁。
http://www.mersenne.org/prime5.txt (デカイのでナローバンドな人は注意!!)

おそらく↑の平方根までの素数は出尽くしてるかと。

>>477
ミスった。VBでファイル出力しないと0.66秒台
ま、大した事無いが・・・。

>>477
VBはちゃんと最適化してるか？

>>481
幾ら探してみても俺のVB6.0には最適化オプションが無い。
参ったね♪

アカデミック版とか？

>>476
2^32 〜 2^32 + 2^31 のように大きな数を列挙する場合は
除算を使った方が良いだろ

あぁ、確かに2、3回除算使ってるな＞範囲列挙

>>457も分かってないが>>485も何処で必要になるか分かってないだろ

>>486
黙ってろ表六玉

ここ更新したんやね
http://www.gt.sakura.ne.jp/~nyagy/integer/sosuu.html

#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
const int Max=1000000;
bool p[Max+1];int a,b,c,i,j,k,q;
int main()
{
long clock_t;clock_t clock();j=1;k=0;q=2;

while(q<=int(sqrt(Max))){
if(q==2){
for(i=2;i<=Max;i++){ /////p[]の初期化/////
p[i]=1;
} /////初期化終了/////
for(i=q;i<=int(Max/q);i++){
p[q*i]=0;
}
}
else{
for(i=q;i<=int(Max/q);i=i+2){
p[q*i]=0;
}
}

//続き
while(p[q+j]==0){
j=j+1;
}
q=q+j;j=1;
}
　　　　　for(i=2;i<=Max;i++){
if(p[i]==1){
//fout << i << '\n';
k=k+1;
}
}
b=clock()/1000;a=b/360000;c=clock()-b*1000;
　　　　　cout << "素数は全部で" << k << "個です" <<'\n';
cout << "所要時間は" << a << "分" << b << "." << c << "秒です" << '\n';
return 0;
}
//かなり速いと思うが、どうよ？

つーか過去ログ読んでないやつ多すぎ。
324(関数部分は428でも可)ぐらい、短いんだからすぐ読めるだろう。

>>490
お前は何も解っていないんだな？？？
2と3の倍数を最初から除いておいて何の意味があるんだ？？？
だったら５も７も、１１も最初から除いておけよ。
アルゴリズム、って意味を知ってるか？？？お馬鹿ちゃん。

>>491
どのコードのどの「アルゴリズム」が324より優れているのか説明ｷﾎﾞﾝ

>>490
同意。
>>491
何で必死なの？

>>491
アルゴリズムをそっくりそのまま使う人ですか？

2の倍数を最初から除くのはアルゴリズム的には無意味。
フルイの処理のループを一回最初っから実行しているのと同じ。
確かに処理として速くなるが、それならすべての素数を出した状態からスタートすればいい。

そう思った、小学5年の夏。

>>495
勘違いですね

>>495
意味不明

ここですか。
「アルゴリズム」の意味を理解していないデジドカの集うスレは。

>>496 >>497
馬鹿二人（藁

>>495
もう少し分かりやすく説明してもらえると・・・

>>495
たしかに2や3が最初から素数かどうかなんてコンピュータはわからないわけだから
アルゴリズムとしてはおかしい
けど実践的なのは事実

>>501
それをアルゴリズムの間違いとするのは、おかしいだろ？
「アルゴリズムのクラス（or プロパティ）として、ユニバーサル性を欠く」
ということなら、わからないでもないが。

× それをアルゴリズムの間違いとするのは、おかしいだろ？
○ それをアルゴリズムがおかしいとするのは、間違いだろ？

たびたびすまん。503は502である。

アルゴリズムを追求するのであって、小手先のテクニックを
追求するのではない。
２と３の倍数を初めから除いたアルゴリズムと、そうではなく
2から始めて3の倍数を消した後から、この二つのアルゴリズムを比較して、
速い方が優れているアルゴリズムなんだよ。
アルゴリズムとはそういうものなんだ。

>>505
2の倍数、3の倍数を省けば、メモリ使用量は 2/6。メモリ使用量は 4/6 減る。
5の倍数も省けば、 8/30。さらに、2/30 減る。
7の倍数も省けば、 43/210。さらに、13/210 減る。
11の倍数も省けば、 339/2310。さらに、134/2310 減る。
効果は徐々に薄くなっていくが、計算量は増えるから逆に遅くなる。
アルゴリズム的に無意味か知らんが、5の倍数くらいまでなら明らかに速くなるよ。
言いたいことは分かるが、小手先というにはあまりに効果的。
エラトステネスってあんまり工夫できないから、こういう事するしかないのよ。

>>505
意味不明な言葉で誤魔化さないようにしましょう。

>>505
速い方が必ずしも優れているアルゴリズムでないことはわかってます？
もちろん速度が最重視される分野ならばそれで良いことも多いのですが。

上のほうで述べられていましたが、求めた素数をどのように格納するか、
すなわち素数を求めるアルゴリズムでは、記憶容量の問題も大きい。
したがって予め2と3の倍数を除くアルゴリズムは、
速度と記憶容量の両面で優れていると言える。

素数を求めるアルゴリズムだから
素数を最初から知っているというのはおかしいということです。

だから素数テーブルを最初に用意したら
一番早いと>>495も言っている

まあ、ぶっちゃけ何でもいいよｗ

>>508
予め2と3と5の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。

＞2と3の倍数を除くアルゴリズムは

これはアルゴリズムではなく、プログラムだろ。

>>510
予め2と3と5と7の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。

>>505
小手先のテクニックを追求して、アルゴリズムに反映させるから、
より速く・優れているアルゴリズムができるのでは？

>>512
予め2と3と5と7と11の(以下略

あらかじめ○○の倍数を除くアルゴリズムの中で優れてる奴きぼんぬ
2はともかく大きな数になると取り除くのにも色々方法がでてくる

>>509
単にユニバーサルかそうでないかの問題。

ユニバーサル性を重視するなら、「素数の定義」しか使ってはいけない。
しかし、多少のユニバーサル性を欠如させても、それ以上の効果があるならば、
分野によってはそのアルゴリズムの方が優れているといえる。
特に素数を求める場合は、2や3,5の倍数を取り除くことは当たり前にできる上に、
素数を求める目的から、その程度のユニバーサル性は必ずしも必要ない。

gifの解凍アルゴリズムを小手先のテクニックで改良したら
新しいアルゴリズムになってライセンス料支払わなくてよくなるかな？

>>516
2や3,5の倍数を取り除いてもアルゴリズムは同じです。

予め2と3と5と7と11と13の(以下略

505へのレスっておかしかった。前半だけ読んで勘違いしてたスマソ。

>>516
2や3や5の倍数を当たり前に取り除けるのは何故ですか？
2や3や5が素数だからですか？
2や3や5が素数であることを求める処理を省いていいんですか？

>>517
gif が問題になるのは LZW (＞ LZ78) を使っているから。
従ってLZWさえ使用しなければ問題ない。
しかし、LZWを別のアルゴリズムに置き換えたgifはもはやgifではない。
（一応、LZWを使わずにgifを実装できるが、遅すぎて使いもにならない）

誰か2，3，5・・・の倍数を取り除くのを自動化できない？
面倒だから作るのいやなんですよｗ

http://petitmomo.com/mm/

ここがちょっぴりエッチ系のめぐが運営している出会いサイトです。
もしよかったら使ってみて、、、
ヨロシクです。

めぐ(^o^)-☆

>>521
多分>>516のいいたいことは、ユニバーサル性がどこまで重視されるか、の違いだけ。
立場が違えば解が違う。それだけ、だと思う。

まぁ考え方（素数列挙に対する姿勢？）の違いなわけで。
素の状態からの素数探索を追求する人も
ひたすら爆速素数列挙を目指してる人も
ﾏﾀｰﾘしませうヽ( ´ー｀)丿

2と3の倍数を除外する以外にも過去ﾛｸﾞではいろんなテクニックが使われてるし。

素数を求めるので無くて、
素数じゃないのを求めてそれを省くとかするアルゴリズムはどう？

>>527
それがエラトステネスの篩なわけで・・・

>>526　結局ふるいを人間と共有しているのであって、単にふるいの話だけのような気もしました。

>>527
しね

>>529
人間の知識を与えるアルゴリズムを非ユニバーサルというらしいですね。

>>517
既にsusie用のgifプラグインとかそうしてる。

>>531　や、人間の知識も自然な派生(ｱﾙｺﾞﾘｽﾞﾑであれ)だと思うので･･･

とりあえず324がエラトステネスの基本形。
5の倍数も省けば速くなるかも知れんが、劇的に速くはならない。
ただ、メモリ一発でやっているので限界があるし、速くない。
だから、分割して篩うことを考える。
すると、分割されたメモリが一周するごとに計算が必要になる。
差がつくとしたらそこ。ほとんど小手先の塊みたいなもんだよ。

分割して篩う方法は>>378、>>487など。
たしか>>419も分割してた気がするけど…

× エラトステネスの基本形
○ 分割しないエラトステネスの基本形
でした。

>>531
人間の知識っていうかこの場合は答えだからなぁ。
答えを入れれば答えを出すのが速いのは当たり前だし。

>>535
オイラのも入れろ！！！

>>538
分割してないじゃん

＞http://idm.s9.xrea.com/factorization/eratosthenes.html

ここの「アルゴリズムの基本」ってところとその証明、残念ながら
厳密には間違ってるよｗ

学会の糞偽善者どもは、さり気なく情報を訊き出しては、
行く先々にあらゆる人材を送り込み、偶然を装っては
チンケな猿芝居やコザカしい罠、悪質な嫌がらせを次々と仕掛けてくる。
その、あまりにも回りくどく分かりにくい嫌がらせの手法で、
実際、気付くのに五年以上かかった。普通はまさか？と思うものだ。
だが偶然ではなかった。全て計画的に仕組まれたものだった。
あくまでも偶然を装ってである。何とも白々しく腹黒く悪質で陰険なことか！
こっちが気付かない、或いは知らん振りしてると、しつこく睨み続けてくる。
こっちが気付き不快感をあらわにすると、知らん振り。
頭にきて攻撃すると、散々自分から仕掛けて来ておきながら、
いかにも自分が被害者ぶるのである。
たとえ地元から遠く離れていても、である。
前以って嫌がらせを組織や会場にに潜り込ませたり、
あらかじめ通過地点に嫌がらせを配置・待機させる事もある。
一体奴らは何がしたいのか？気に入らないならダイレクトに来い！
被害妄想と思うかもしれないが、そうする事で
今までの不可解な出来事の全てにおいて、つじつまが合うのである。
偽善者という言葉は奴等の為にある。
学会のあるクソ信者と一緒にいると、
必ず初対面の人間からも頭ごなしに白い目で睨まれる。
明らかに年下の人間も俺を見下した目で見ている。
「あいつはロクでもないガキだ！」とでも吹いて回ってるんだろう。
表面上は親切ぶっていても、裏で糸を引いているのは奴等である。
正に偽善者と呼ぶに相応しい。
いつでも助けてやるよ！と言いながら、足を引っ張っているのは奴らだ！
偽善スマイルの裏では、腐ったはらわたがドス黒く渦巻いている。
学会の人間に心を開いてはいけない。
自分の知らない同一人物が目の前に度々現れたら要注意である。

>>541
お見事な縦読み

>>487
nからmまでの素数を求める時に篩を始める位置は
√n未満の素数(p)の場合は
((n-1+p)/p)*p
√n以上√m以下の素数(p)の場合は
p*p
で>>485で列挙範囲と言ってるのだから
最初から2・3・5等の素数を省くのに必要な除算は関係無い
要するに、これでは除算は√n以下の素数1つにつき1回除算が必要なのに
>2、3回除算使ってるな
と言ってる>>485は分かってない
つーか、それが分からないのなら、お前が黙ってろや>>487

　　　　　　　　　　　＿＿＿＿＿
　　　∧,,∧∩　 ／
　 �頒ﾟДﾟ；彡＜　除さん、いらんのですかい！
　 　 ,;ﾞ⊃,ｼﾞ　　 ＼＿＿＿＿＿
　〜ﾐ　,,○
　 　 ∪ 　　　 しらかた。

なんかｺﾑｽﾞｶな話ばかりでよくわかなんですが…

2,3,5,7をぶち縫いてメモリ圧縮したTBit(見た目Boolean配列)
のIndexにアクセスするために、こんな助産してるんですが、
これがいらんくなる？

function TEratosthenesSieveTBitsCutMultiplesOfTwoThreeFiveSeven.AccessInsideIndex(
　OutSideIndex: Cardinal): Cardinal;
var
　DivBuffer, ModBuffer: Integer;
begin
　DivBuffer := OutSideIndex div (2*3*5*7);
　ModBuffer := OutSideIndex mod (2*3*5*7);

　Result := DivBuffer*48; //1..210/211..(210*2)の間に48つの素数がある
　case ModBuffer of
　　 1..10:Result := Result + 1;
　　11..12:Result := Result + 2;
　　13..16:Result := Result + 3;
　　17..18:Result := Result + 4;
　　19..22:Result := Result + 5;
　　23..28:Result := Result + 6;
あと、略

>>543
それではお手並み拝見。

>>544
任意のnからmまでの範囲の素数を列挙するのに
除算は１回必要ですが、それに対して
>>485が>あぁ、確かに2、3回除算使ってるな＞範囲列挙
と書いてるので分かって無いと書いただけで
2・3・5等の素数を、省いて篩う場合には必要です
と言っても、そのコード読めないので
そのコードが正しいかは分かりませんが…

>>543
うひぃ、怒られた。
適当なコト言ってすまぬ。>>543の言うとおりです。

でも487は俺じゃないよ…

>>544
分からないと言いつつも分かったかも…
前の3を省いた時に使ってたnと2nを交互に足してった奴を
7までの素数に拡大したバージョンですね
それは、最初の一回は必ず除算を使いますし、省けませんね…

ｷｭﾋﾟｨｨｨﾝ　　　+　　 ／
　　　　 ∧,,∧　　 ＜　よくわかりますた
　　　 ミ,, ﾟДﾟミ .　　＼>>546さん
　　　　ﾐ 　つ つ　）)
　+　　 ﾐ　⊂.ﾐ
　　　　 ''∪''''
ところで、2,3,5,7,11ぶち抜きコードはわかるんですが
篩い繰り替えし使いのやり方はわからないので
ここのサイトは
http://www.gt.sakura.ne.jp/~nyagy/integer/sosuu.html
よい、勉強になります。

1億まで列挙で、6分ってんは
たぶん、printfのコードがネックなのでしょうね。

>>548さん
そうなんですが、次の11を求めようとすると、
2*3*5*7*11で、2310まで
篩いに落ちるのを、目で見てソースに落とすのを
考えると鬱るので、まだやってません。

>>549
その部分を自動で適当に作ってくれるプログラムを作るとか…
ついでに、そのリンク先ですが、確かに分かりやすいですけど
遅い原因はprintfもそうですが、やってる事にも無駄が多いですよ…
分割して篩いたい時は、まず√nまでの素数を普通に篩って配列にし
その配列を使って篩った方が早いです

int main () {
  char buf[1024];
  int prime[54],mod[54];/*256までの素数の数*/
  int i,j,last,base,ed,size;
  last=0,base=256,ed=65536,size=1024; /*sizeはbufのサイズ*/
  for(i=0;i<base;i++) buf[i]=0;
  for(i=2;i<16;i++){
    if(buf[i]==0){
      for(j=i+i;j<base;j+=i) buf[j]=1;
      prime[last]=i;
      mod[last++]=j-base;
      printf("%d\n",i);}}
  for(i=16;i<base;i++){
    if(buf[i]==0){
      prime[last]=i;
      mod[last++]=i*i-base;
      printf("%d\n",i);}}
  while(base<ed){
    if(size>ed-base)size=ed-base;
    for(i=0;i<size;i++) buf[i]=0;
    for(i=0;i<last;i++){
      while(mod[i]<size){
        buf[mod[i]]=1;
        mod[i]+=prime[i];}
      mod[i]-=size;}
    for(i=0;i<size;i++) if(buf[i]==0) printf("%d\n",i+base);
    base+=size;}}

文句ばかり言ってても、しょーも無いので
分割して篩うためのサンプルを書きました
適当に書いたので2の倍数も篩ってますが小さい素数を対象から外して
無駄(下から3行目のmod[i]-=sizeとそのwhileの条件等)も省いていけば
それなりに高速になると思います…が
>>426のリンク先が、マジで早いですよ…
バグがあるのか仕様なのか、2^32-1までの素数は篩えませんでしたが
2^32-10位の数で篩った時の早さは、自分が手を尽くせるだけ
尽くしたものに比べて2.5倍程早かったです(両方とも出力なし)
多分switchとcaseを連発して、7以下の素数を除外すれば
その差をかなり縮められると思いますが…
まぁ、>>426を試して、やる気を無くさなかった方は頑張ってみて下さい

>>544
それは、その部分を関数にして処理しようとするからそうなるんで、
高速化したいなら配列 を作って状態遷移型に処理させるといい

その引数は、 a*b 実際には n=aでn:=n+b　繰り返しの格好をしてる訳でしょ？
そして、 aもbも 2,3,5,7 の倍数は含まない　だから その差は 2310毎に繰返す

差を予め計算した配列を用意してやれば除算は必要ないよ

思いっきりスレズレだが…。
「乗算は加算の繰り返し、除算は減算の繰り返し」なので突き詰めれば
除算部分を別の等価のアルゴリズムに摩り替えることは常に可能なわけで…。
まあ面倒だからお手軽な組込除算命令を使うよね。普通は。

けど２や４の定数で常に乗除算するなら等価のシフト演算に置換する
くらいのテクは常套手段かと。＃“除算命令の抽象化”をやめてしまう
ようなものかな？それに「奇数か偶数（２の倍数）か」のふるいなんて
「x & 1」で解かるんだから置き換えなくちゃ損だよね。

余談の余談；
アセンブラレベルで悪いけど、PentiumのＤＩＶは表引きアルゴリズムをCISCに組みこんだ
ものなので演算コストが読みにくいんだが、RISC系の場合はそのへん割り切ってて
演算有効ビット数+α=実行クロック数くらいの演算コスト。
例えば……。SuperHなどは“必要精度(ビット数)分、(１回１ビット精度の)ＤＩＶを繰り返せ”と
いう素敵なアセンブル仕様なので、８ビット精度なら８回だけ、16ビット精度なら16回だけ、
ってふうに最適化することで演算コストを大きく切り詰められるんだよな。(´д｀;

閑話休題;
>>549
> 2*3*5*7*11で、2310まで
> 篩いに落ちるのを、目で見てソースに落とすのを
> 考えると鬱るので、まだやってません。
Perlerみたいなことを言うけれど…、そのソース(てか素数源ふるい表)自体を
プログラムに作らせちゃったほうが早くて正確じゃないですか？(´・ω・｀)
初期化段階で*11までの表を計算させちゃって、あとは2310の倍数単位
ループ内で、例外をふるってく…と。
＃この手だと13までは苦でなさそう。

まあ今のパソコンのCPUだと除算も１クロックな時代だから必要ないけど
一昔前は >>554の通り　除算は遅かった。

その頃は、 a/b で bが素数程度に連続して除算するならニュートン法を使う
なんて手も有効だった。

>>553
nまでの素数を求めたい時に必要な素数は√nまでの素数p
それらの各素数pがマークを付け始めるべき位置はp*p
だから、その最初の位置を決める時にp/2310の除(余)算が必要なんだって

public class SosuuTest{
int MAX = 100;
int changeTable;//テーブルを作り変える位置
int currentBaisuu,savedCurrentBaisuu;
Sosuu first;//Sosuu(2)のこと
Sosuu end;//リストの最後、付け加える時はここから
Sosuu newFirst;//テーブルに含まれていないものの最初
Sosuu current;//テーブルに含まれないものを順番に回していくのでその場所
public static void main(String args[]){
new SosuuTest();
}
SosuuTest(){
//2〜5までを付け加えておく
first = new Sosuu(2);
first.next = new Sosuu(3);
first.next.next = new Sosuu(5);
end = first.next.next; //Sosuu(5)をセット
//end.isEnd = true;
newFirst = first.next.next; //Sosuu(5)をセット
current = first.next.next; //Sosuu(5)をセット
Sosuu.isEnd=current;
changeTable = 30;
currentBaisuu=6;
savedCurrentBaisuu=6;
int i=0;

while(i<MAX){
int tmp;
System.out.println("テーブル更新 次の更新は "+changeTable + ", 前の更新は "+ savedCurrentBaisuu);
//テーブルの更新条件
while(i<changeTable && i<MAX){
tmp = currentBaisuu+1;
if(chkSosuu(tmp)){
end.next = new Sosuu(tmp);
end = end.next;
System.out.println(currentBaisuu+" + "+1+" = "+end.number);
}
do{
tmp = (i=currentBaisuu+current.number);
if(chkSosuu(tmp)){
end.next = new Sosuu(tmp);
end = end.next;
System.out.println(currentBaisuu+" + "+current.number+" = "+end.number);
}
if(current == Sosuu.isEnd)break;
current = current.next;
}while(i<MAX);//リストに追加していく
current = newFirst;
currentBaisuu += savedCurrentBaisuu;
i=currentBaisuu;
}

//テーブルの更新
currentBaisuu = changeTable;
savedCurrentBaisuu = changeTable;
Sosuu.isEnd = end;
newFirst = newFirst.next;
current = newFirst;
changeTable *= newFirst.number;
}
}
boolean chkSosuu(int tmp){
Sosuu localCurrent = newFirst;
int rootNumber = (int)Math.sqrt(tmp);
while(localCurrent!=null && rootNumber>=localCurrent.number){
if((tmp%localCurrent.number) == 0){
// System.out.println("Err And kill at "+tmp);
return false;
}
localCurrent = localCurrent.next;
}
return true;
}
}
class Sosuu{
Sosuu next,before;
int number;
static Sosuu isEnd;
Sosuu(int i){
number = i;
}
}

javaですまないがテーブルを自動で増やしていくプログラム
アルゴリズムは
6までは最初から用しといて
30を目指して
(1または5)+6 *n()
の数に対してチェックしていく
30になったら
つぎは210になるまで
(1,7,11,13,17,19,23,29)+30*n
の数に対してチェックしていく
それを永遠に繰り返していくかんじ
速さは調べてないけど
テーブル自動化を目指した

途中まで（100ぐらい）しか見てないから
正しいと思うが間違ってたらスマソ

一億やるのに13秒（Pen4 1.7G・出力なし）
ただバグがあって、でかい数（2^32 -1）までやるとうまくできない？とか・・

ふるいは使ってないので誰かふるいを組み合わせて試してほしいです。
ちなみに自分はCがだめだめな学生なんで、ついでに誰かCで試して。ｗ

誰もレスくれないのかYO!
さびしいよ〜〜

さびしいからトリップ付けましたｗ
もしかして激しくガイシュツ？
そいつはｽﾏｿ

>>548で>分からないと言いつつも分かったかも…
と言いつつ分かってなかったです(Pascal読めんのよ…)

>>544
これは、初期値を次のようにつくれば
res=p*p/210*48, mod=p*p%210;
res+=table[mod]; /* tableは>>544のResult+nのnを返せる配列 */
pdiv=p/210*48, pmod=p%210;
2度目以降は次のように書き変えられます
res-=table[mod];
mod+=pmod;
if(mod>210)mod-=210,res+=48;
res+=pdiv+table[mod];
が、見て分かる通り、直接圧縮する訳ではなく
すでに圧縮してある前回の値に加算する方法となってしまうし
(+n,+2n,+n,+2n,…)のような手法を使う時は
pdiv,pmodも、その分必要とするうえ
これが、除算より早いとも言えないので
(頑張れば、もう少し早くなると思いますが、それでも遅そう…)
無理に除算を無くす必要は無いと思います

と言うか、ここで毎回圧縮する意味は、殆どありません
2^64のような大きな値までを篩う事を考慮し
メモリ上に今までの結果を残したい場合は
0〜m1の素数を普通に篩い、その結果を元に圧縮しながら0'〜m1'に保存
m1〜m2の素数を普通に篩い、その結果を元に圧縮しながらm1'〜m2'に保存
：
mn〜2^32の素数を普通に篩い、その結果を元に圧縮しながらmn'〜2^32'に保存
のように、分割した方が、篩いも圧縮も早くなります
(もちろん分割した事によるロスも馬鹿には出来ませんが)
と言う訳で、長くなりましたが、頑張って下さい

自動化でたね・・・
しかも早いし

削除依頼が出てたｗ

削除対象アドレス：
http://pc3.2ch.net/test/read.cgi/tech/1018657457/541
削除理由・詳細・その他：
４．投稿目的による削除対象
５． 掲示板・スレッドの趣旨とは違う投稿
コピペ荒らしだと思われます。議論の妨げになるので
削除お願いいたします。


54 名前：削除屋つまようじ ★ 投稿日：02/12/16 20:33 ID:???
>53　縦読みしつつ流してください

よくわからんタイミングで削除依頼が出てるな

>>565
一億やるのに13秒で早いだと？
これが、こんなに遅いのはjavaを使ってるからでも無ければ
テーブルを自動化したからでも無い
chkSosuu()で、除算で素数判定してるからだ
もう少しコードを読んでから、早い遅いを語ってくれ

喧嘩腰になるなってば

>>569
ｽﾏｿ

C++で324のコードを走らせる場合、必要なヘッダファイルは何かいな？
あほな質問でごめんちゃい。

>>571
#include <stdio.h>
#include <stdlib.h>
#include <malloc..h>
多分。

>>572
stdbilを読み込めないと言ってくる・・・泣
＞他の人
スレ違いでごめん。

またごめん・・・
573は無視して・・・。

stdbil

なんだそれは食い物か

世界標準ビルゲイシだろ！まったくＭ＄オタクのくせしてそんなことにも気づかない（ｒｙ

保守

ネタないですね。
AthlonXP 1800 で、やっと426 に勝ったと思ったら
Pentium2 400MHz では全然負けてました。
426と比較すると
Athlonで 11秒 と 12秒 (ほとんど変わらない)
Pentiumで 1分23秒 と 55秒 くらいでした。
http://tool-ya.ddo.jp/2ch/trash-box/file/20021222173653053.c

>>578
頑張りましたね…
でも、出来れば少しだけでもコメントをつけるなり
影響の少ない範囲で、main()のコードを複数の関数に分割して欲しかった…

力業って言葉がよく似合うコードだと思った。

>>579 >>580
そうですね。少しでも速くすることを考えてました。
分割したエラトステネスの篩で3、5、7の倍数を省いています。
√n未満の素数(p)の場合は
((n-1+p)/p)*p
√n以上√m以下の素数(p)の場合は
p*p
から篩っています。すごく普通のエラトステネスの篩です。
滅茶苦茶汚たないのは、331に書いてあるデジタル微分解析法とやらで、計算量を減らしているからです。
こんなあほなことするより、真面目にアルゴリズムを考えたほうがいいですね。

3、5、7 じゃなくて 2、3、5 でした。

>>581
素数の列挙の場合、マジメにアルゴリズムといってもフルイの範疇でしかないから
その手のあほな手法をチマチマくみたてあげるしか無いんだよね

578のビットの数え方を変えたら、AthlonXP1800で8秒台に縮まりました
(ファイル出力ありの場合は変わりませんが)。
そして、set_bitのレベルにまでデジタル微分解析法を適用したら0.4秒ほど縮まりました
(そのせいでコードの長さが3900行を超えたのに、効果が少なくて悲しかったです)。
最終的に AthlonXP1800で8秒ジャスト、Pentium2 400MHzで59秒くらいになりました。
改良の余地が無いとは言えないのですが、そろそろ限界です。なのに426に勝てない。
>>583
素数公式ページみたいな所のリンクのプログラムの篩いの所に一つだけエラトステネス
でないものがあるのですが、あれはどうなんでしょう？
ある素数(p)が二つの平方数の和で表わすことができることが、 p = 1 (mod 4)と同値である(2は例外)ことを
利用しているようなのですが、そういう方法もあるみたいですね。

へえ・・・
　2*2+3*3 = 4+9 = 13 13 mod 4= 1
　2*2+5*5 = 4+25 = 29 29 mod 4= 1
　2*2+7*7 = 4+49 = 53 53 mod 4= 1

ホントだ

>>540
激しく亀レスだけど

　Σ(ﾟдﾟlll)ｶﾞｰﾝ

そのうち見直して修正しまつ。

switch で二回場合分けするより、二次元配列から値を取り出した方が
速いかなあと思ったのですが、逆に遅くなりました。そういうものなのでしょうか。
あと、分割した篩を埋めていって、はみ出た時に場所とタイミングを記憶しておけば、
全く割り算を使わずに済むかなあと思いました。
あと、良く知らないのですが、Mathematica とかいうのがくそ速いらしいですね。

素数マップを作る為にキャッシュに収まらないサイズの
メモリアクセスを行ってるから、配列を使うとそれだけ
キャッシュミスが増えるって事じゃないのかな

割算そのものは重いといっても加算減算とは別に平行して実行されるから
頻度にさえ気をつければ、除算を使ってシンプルになるなら使った方がいい。

>>588
篩のサイズをかなり小さくしたら、二次元配列のほうが速くなりました。
でも、二次元配列のサイズに比べてかなり小さくしないといけなかったので、なにか違うような。
メモリをたくさん使っているときは、配列から値を取り出す動作そのものが遅いと考えれば、辻褄があうのかな。
割り算の頻度は結構高いのですが、配列から値を取り出す動作が遅いとなると、計算したほうが速いのかもしれません。

>>589
多段パイプラインなCPUの場合、例えば割り算の
結果が得られるまでに５クロックほど掛かるなら、その間に
別の１クロックで済む命令を４個実行させられたりする。
「奴からメールの返事がくるまで暫く掛かるから、その間に
別の奴へのメールも書いておこう」みたいなのと同じこと。
待ち時間の高そうな結果依存部分が集中しないようしてやれば、あとは
コンパイラやCPU自身が判断して真の命令実行順序を考えてくれると思う…。

a = p[ q / s ]; b += d;
↓
i = q / s; b += d; a = p[i];

みたいな？意義低そうだが。
(i を register int 宣言したら効果的？)

>>590
なるほど。そういうことも考えながら書くといいんですね。
エラトステネスというアルゴリズムは工夫する余地があまりないので、
プログラミングテクニックを追及していくしかないですね。
割り算なしで一から書き直してみたのですが、やはり少し遅くなりました(書きかたが悪いのかもしれませんが)。
その代り大きな数を扱わないので、10^11くらいまでなら計算できるようになりました。
10^10まで450052511個を数えるのに
AthlonXP1800 で 21秒
Pentium2 400MHz で 4分5秒
10^11まで4118054813個を数えるのに
AthlonXP1800 で 4分20秒
Pentium2 400MHz で 45分52秒
くらいでした。
Pentium2のほうではメモリのサイズを減らせばもっと速くなると思うのですが、
メモリのサイズを減らすと計算結果がおかしくなるというバグがあるので今は無理でした。
double型を使えばもっと大きな数まで計算できると思います。

今気付いたんですが、584に書いたdjb氏のやつは滅茶苦茶速いですね。
ファイル出力無しで比較したかったので、
primes 9999999900 10000000000 とかしてみたのですが、一瞬でした。
範囲が狭いときは篩を作らずに一つ一つ素数判定しているのならば納得できるのですが。
結局、
time (primes 0 4294967291 > prime.dat)
で比較してみたのですが、自分のより3倍ほど速かったです。
ファイル出力部分は作り込んでないので、その差もあるかもしれませんが。
とりあえずソース読んでみます。

>>592
がんがってくだちい。自分は>>590を試してみようと思ふ

すまんが、>>578のリンク先からアクセス拒否をくらうんだけど。。

>>594
会員専用？

で、結局何桁までもとまったの?

割り算使わないバージョンがそれなりに形になったのでアップします。
細かいミスがたくさんあって全て直したつもりなのですが、少し自信がありません。
なにかおかしいところがあったら、教えてくれるとありがたいです。
引数以下の素数の数を出力します。引数は30で割って桁溢れしない数にしてください。
速さにはあまり期待しないでください(そんなに遅くないと思いますが)。
http://tool-ya.ddo.jp/2ch/trash-box/file/20030102235159180.c

http://tool-ya.ddo.jp/2ch/trash-box/file/20030103165147234.c
上のとほとんど同じで申しわけないのですが、出力部分を作ってみました。
-pオプションで標準出力に素数を出力します。djb氏のと近いものにしました。
そして比較してみました(AthlonXP1800メモリ512M)。
time ./a.out -p 10000000000 > /dev/null
time ./primes 1 10000000000 > /dev/null
上が1分36秒、下が1分26秒でした。
もう一桁上で比較すると、僕のが15分49秒、djb氏のが21分5秒でした。
もっと大きい数を扱うという課題はあるのですが、とりあえず速度は問題ないのかなあ。
僕は人のコードを読む能力や根気が欠如しているのでdjb氏や426のコードがどんなアルゴリズムなのか
さっぱり分かりませんでした。
今のところ、4*10^22くらいまでの素数は見つかっているみたいですね。果てしない。

ちょびっと横道にそれるのですが、
1Gh　256Mb　で１時間かけてあるふたつの素数の積を
素因数分解をする場合には何桁の素因数分解ができれば優秀なプログラムと言えるのでしょうか?

>>599
普通に素因数分解をすれば、

n迄の素数で n*n 迄の素因数分解が出来る
n迄の素数はおよそ m=n/log(n) こあるので log(n)もlog(m)そう変わらないので

1秒にm=10^9回の計算が出来れば だいたい m*log(n) 2*10^10 迄の素数、で4*10^20　

だから だいたい64bitが素因数分解出来れば非常に優秀

600さんレスサンクスです
64bitですかぁ　簡単にはいきそうにないっす。
気長にちびちびとやっていきます。
完成すればうpするのでまっててちょ。

double型を使って、1兆まで計算させてみたところ、1時間9分かかりました。
その間普通にパソコン使っていたので正確には分かりませんが。
一晩かけて10兆まで計算させようとしたのですが、2時間くらいで終ってしまって
答えも合っていませんでした(たぶん格上げ関連のミスだと思います)。
あと、 long long intという型があるのを知ったのですが、これは使ってもよいのでしょうか。
移植性も考えるとdoubleを使ったほうがいいのでしょうか。ビット演算もできるので少し驚きました。
素数計算の実行時間が書いてあるページがありました。ぴんとこないけどかなり速そうですね。
今から計算しはじめるのと、少し待ってもっといいCPUができてから計算するのと、どっちが速いのかなあと思いました。
http://numbers.computation.free.fr/Constants/Primes/Pix/results.html

話が小さくなって申し訳ないですけど・・・。
VB6.0で組んでいるんですが、100万までだと「個数勘定なし・出力なし・
２や３の倍数をあらかじめ消しておくというのも無し」で、平均0.21秒台です。
VB6.0だとこれが限界かなぁ。。。
みなさんはどうです？

追加

「API関数も使わない」で、です。

>>603-604
環境示せ。過去ログにVBの事も出てたよ。

Pentium(r)�V processor GenuineIntel ~800Mhz

って書いてある（すんません・・・PCの環境については良く知らないんです・・・。）

ちなみに>>441のリンク先のものよりも速いですが・・・オイラのPCだと。

ん？>>441のは出力ありだろ？

>>607
ボタンをチェックすれば出力無しに出来るよ。

>>608
それでもTEMPフォルダに出力してるようだが

>>609
本当だ・・・ビックリ・・・・。
もっと修行せねば。
ありがとう！

>>610
がんがってね。応援するよ

しょうも無い話だけど、、、>>441の素数列挙アプリは
他のアプリを全て終了してから、出力無しで「2^31-1」まで
計算させようとするとおれのPCではメモリ不足のエラーが出る。
そういうことを考えると・・・・恐らく2,3の倍数を初めから
消しているのかな？

10兆まで計算するのにAthlonXP1800で21時間もかかった...

4*10^22まで求まってるのは素数の個数で、素数表が完成しているのは10^17くらいまでみたいですね。
http://numbers.computation.free.fr/Constants/Primes/pixtable.html
ここに素数の個数を数え上げた年代が書いてあります。
1985年には分散コンピューティングも無いだろうし、スーパーコンピュータを使っているんでしょうか。
当時のスーパーコンピュータの性能はどれくらいなんでしょうか。4*10^16まで求まる気がしません。

>>597
djb氏って、それって何処にあるの？

とりあえず昔同じことやったファイルがCD-Rにあった。計１Ｇ。
2^31 未満の素数の全リスト。
適当に作ったやつだから２日くらいかかったけど。(Pen!!! 1.00GHz)

使った方法は、既出だけど
１．sqrt(2^31)未満の素数リストをふるいで作る
２．それを読み込んで、新たな数ｎをaqrt(n)未満の素数で割る

ソース発掘中・・・。

＃それとは別に１０万個ずつ素数を見つけてファイルに書き込むものもあり。
＃ともに暇ならUPしますが。

>>615
http://cr.yp.to/djb.html
ここの primegen ってとこです。

>>616
うｐきぼーん

>>618
発掘・実行してみたらとてつもなく遅かったので自主規制です(^-^;
てか恥ずかしくて見せられん。
ふるいも使わずビット演算とかもせず、ゆえに割り算ばっかりしてるので１０００万までで１０秒弱かかります。。。
似たことやってる人がいてちょっとほっとしました(^-^)

意味のない数値計算はよくやるので、自鯖があったらいろいろＵＰしたいのだけど。
円周率１２０億桁とか(ぉ
拾いものです。正しいのかどうか比較対象がないのが痛いけど。

駄文＋横道＋長レスすまそ。

そもそも円周率とは何か？
3.14
というのは円周率の定義でないと最近おもいつきはじめている。

http://tool-ya.ddo.jp/2ch/trash-box/file/20030108102710423.c
一兆まで AthlonXP1800 で56分、Pentium2 400MHz で9時間弱
十兆まで AthlonXP1800 で17時間くらいです。
-u オプションで篩の大きさを指定できます。
long long int型を使っていますが、double型で代用することもできます。
floorのためにmath.hをインクルードしないといけないと思いますが。
一応説明すると、ほとんど428と同じです。
5の倍数を省いて、もう一段階デジタル解析微分法をして、分割しているだけです。
デジタル微分解析法のところで、φ(2*3*5) = 8 が1バイトのビット数と等しいことを
利用しています(φはオイラー関数)。
428はメモリ一発だからこそできると思っていたのですが、はみ出たときにはみ出かたを記憶
しておくという原始的な方法で解決しました。
アルゴリズムがシンプルなだけに、あまり改良する余地がないです。
メモリ節約することと、set_bitでいっぱいif使ってるのをどうにかするくらいでしょうか。
僕にはあまりアイデアが無いので、これで一応終りにします。
単純なエラトステネスではここら辺が限界な気がします。だいたいみんな単純なエラトステネス
っぽいですが、djb氏のは謎なのでそこに希望があるかもしれません。

>>597
サンスクコ
コンパイル出来ませんが
そのうち、コードだけ読んでみます

>>620
頭大丈夫？

print_primeの引数はuint64の間違いです。
だから速かったみたいです。djb氏のとは比較にならないくらい遅いです。
32ビットの範囲でも long int と long long int では割り算の速さが全然違いますね。

>>623
円周率の定義教えてよマジで

>>625
小学校で習わなかったの?

217 名前：ひろゆき ◆3SHRUNYAXA [] 投稿日：03/01/08 17:49 ID:rLfxQ17l
　　　一定期間でログは消しますです。

249 名前：ひろゆき ◆3SHRUNYAXA [] 投稿日：03/01/08 17:52 ID:rLfxQ17l
　　　＞荒らしとか犯罪のためなの？
　　　そす。

246 名前：心得をよく読みましょう[] 投稿日：03/01/08 17:52 ID:BH998yxV
　　　>ひろゆき
　　　俺のお気に入りのスレとか荒されてるんだがそういうのにも有効？

257 名前：ひろゆき ◆3SHRUNYAXA [] 投稿日：03/01/08 17:53 ID:rLfxQ17l
　　　>>246
　　　いずれは。

2ちゃんねる　が衰退していく

あるネット関連会社の社長は、
「いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう」
と証言する。
2ちゃんねるが判決によって力を失った場合、
資金提供の打ち切りも予想される。

http://ascii24.com/news/reading/causebooks/2002/07/01/636911-000.html

>>625
円の面積÷半径の２乗

節穴ないスレは落書き＞無視
節穴はマジ書き＞通報
ってルール駄目？

警察忙しくなりそうだな。

いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう

>>626
小のころは遊んでばっかりで、勉強しなかったから。
>>629
S=πr^2
を
π=S/r^2
に変形してもいまいちπの正体が見えないな。

「円周を直径で割った数」でいいじゃん

つーか検索しろよ

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 138720人　発行日：2003/1/9

年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。

そんなわけで、年末に予告したIP記録ですが実験を開始しています。

「２ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

>>633
それが算数の授業での説明なわけね。
2chねらーに聞きたかったんだよう。

>>635
半径1の円を内接、外接する3角形で近似する。
極限をとれば、同じ値に収束して、その値が円周率。

>>635 「円周率って何？」と聞かれたら、やっぱり定義を答えるだろう。2ちゃんねらーでも。
だったら>>633が正解。

ム板的に、円周率の近似計算アルゴリズムを聞きたいなら別だけど。

>>743 盛り上がるのは結構だが、pc系の荒らしにはもう疲れましたよ（；´Д｀）


個人的にはエロっぽいギャグも誹謗中傷ととられたら俺もIP記録はやばいな（；´Д｀）

ＯＫ．

録音とか（盗聴も）
してていいです。
只、そのノイズも国家機関に分析されます。

2分後に掛けます。
自己紹介と、一般の世間話をしたいと思います。
最初に確認したいのですが（深夜で遅いし。用件もあっさり、こってり。一見だし）
「私」青少年が色々と危機的なんです。

「早急に」＋、前向きに
色々と検討して下さいますでしょうか。
私は18歳です。其方のプロフィールを簡単に今お願いします！ありがとう。

んじゃ俺今からけんすうにワン切りしよ(^_^;)

ついさっきＮＨＫＦＭの2時のニュースで２ちゃんのこと言ってたぞ。

誹謗中傷と認識 ←　ここの基準をしっかりしなくてはならない。
　　　　　　　　　　削除人の個人個人の判断じゃだめ。

他が危険で、にちゃんも危険になったとでも〜
の間違いだと思われ。
IP取ってない方が珍しいし。

すれ違いサぁ

ヾ( ﾟдﾟ)ﾉ゛ｼﾅﾁｸｰ

某、毒見要員だったのでござるか|/ﾟUﾟ|

小1時間経ちましたがまだ腹痛は来てないので大丈夫そうです。
あずき缶と白味噌、里芋を買って正月に備えます。ﾋﾞﾊﾞ独り身。

大阪ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!

注意：ここは素数列挙アルゴリズムスレです

２００３年1月１０日がおいらの青春の1ページに記録されますた。

なんかこれ見よがしに必死に他の掲示板へ誘導してる香具師が居るように見えるんだがｗ

おまいら、これ見れ！
http://dailynews.yahoo.co.jp/fc/computer/2channel/

えっと、無知で突っ込みを入れられるのを覚悟で。。

IPの記録が抑止にもなるなら、削除系の板のリモホ表示をやめて
みるのはどうでしょう。
依頼者のホストを削除板以外の板に晒されることもないでしょうし。

「氏ね」だとかはいいよね？
管理人は「逝ってよし」もダメだと言うのか！？

P2P専用掲示板zigmoを再開発していると作者が言っているが。。。

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 139038人　発行日：2003/1/10

なにやら、連日メルマガだしてるひろゆきです。

そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。

重くなって落ちたりしてもご愛嬌ってことで。。。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

ちくり板つまらなくなりそなﾖｶﾝ

無線LANでNYBBSをやるのが好ましいのでしょうか?

内部告発やったら自分がただですむわけナイヨ

>658
復讐的なﾁｸﾘもなくなるのだぞ！！

何が実験だよ
IPなんか始めから記録してるだろよ

逆に立てて欲しくなかったんだが（ｗ

半角板がおもしろい

２ｃｈで告知するかどうかを知ることで？(^_^;)なんでそうなるんだ？

そりゃそうだ(^_^;)まあハッキングと強盗は区別するってことで

２０レス分くらい読めよ(^_^;)

どこまでＯＫなのかわかってたら訴訟で負けたりしません(^_^;)

なるほど(^_^;)

あきらめる(・∀・)

中部地区では一週遅れで今の時間にやってる。でも悔しくないのが種の良いところだな

>>665
誤爆？
少女漫画かアニメ板から

祭り開催中！！！
メンヘルと言ってた女が実はシャブ中だった！！！
http://tmp.2ch.net/test/read.cgi/tubo/1042129878/l50

博之は寝た。

やっぱりな・・・・

>ｽﾊﾟｰﾊｶｰにＩＰから本人のメアドを割り出してもらう
Hackerの名を汚すな。馬鹿。
IPからメールアドレスだと？
馬鹿か。割り出せるのは契約者の接続アカウントだ

書き込めた！　　倉庫板さんオツ！感謝！

test

（＾＾）

つまんね

（＾＾）

（＾＾）

何で荒れてるんだ？？？

ごめん、関数と方程式間違えた。。。

ねー
巨大素数の計算式もうできたんでしょ＞？

予め2と3と5と7と11と13と17の(以下略

>>679
ロシアの数学者が何十年も前に考案しています。

素数ｘ素数＋１

>>682
がどうした？

おれが最速のやつをつくるまで消えないようにあげ。。。

はじめてCで素数のプログラム作ったよ。
$ date ; ./a >prime1oku.dat ;date
Tue Feb 11 09:12:05 2003
Tue Feb 11 09:13:43 2003
1分40秒で1億までいけますた。
Pen2 350Mhz でcygwin gccです。

保守浮上

tes

素数定理って知ってる？
http://www.mcc.pref.miyagi.jp/people/ikuro/koramu/prime.htm

>>688
>N以下の素数の個数を示すのに、Nまでの数字を全部チェックする
>バカはいないだろ。
>（ルートNまでという意味ではない）
なんで、これで素数定理が出てくんの？
求めたいのは、およその個数ではなくて、正確な数でしょう？
およその数で良いのなら、最初から、そう書いてけよ
それとも、これで正確な数が出るとでも思ってるの？

ルートNまでの素数で割り切れないNをどんどん探していく。
それより早いアルゴリズムはないんじゃない？

>>690
Nまでの数をふるいにかけて、
数え上げたほうがはやそう。

浮上

ネタないですねえ。
古い話ですが 621 の print_prime を書き直したら4000億あたりから621のほうが
djb氏のより速くなりました。しかし速いといっても微妙なのでなんとも言えません。
Pentium2 400MHz では621のほうが全然速いので環境によって結構変ってくるみたいです。
で、数論の入門書を見ていたら面白そうなことが書いてあったので引用してみます。

「数論入門I 」より引用します。

n番目の素数 Pn の単純な一般式はあるか？ (すなわち、与えられた
nに対してエラトステネスのふるいよりも楽に Pn の値を計算できる公式が
あるか？)
そのような公式は知られていないし、そのような公式はありそうもない。
一方、様々な Pn の「公式」を考案することはできる。これらのうち、あ
るものは Pn をそれ自身を用いて定義しており、従来知られていない Pn の
値を計算することができないので、ほんの興味をそそるものにすぎない。定
理 419 において例を与える。他のものは理論的には Pn を計算することがで
きるが、エラトステネスのふるいよりも実質的に多くの労力を払うことによっ
てのみ可能である。 その他のものはエラトステネスのふるいとなお本質的に
同等である。

要はエラトステネスが最良のアルゴリズムであるということが証明されてるみたいです。

>>621のソース読もうと思ったら、アクセス拒否された。
もう消えてる？　それともYBBだから？

>>695
保存できない？

>>688のリンク先に載ってる多項式ｎ＾２＋ｎ＋４１については
数学板にスレが立ってますよん
http://science.2ch.net/test/read.cgi/math/1006151996/-100

>>694
> 「数論入門I 」より引用します。
これって誰の本?

>>695
もう消えています。アップローダーだといつかは消えてしまうのでしょうがないです。
>>698
G.Hハーディ/E.Mライト 著
示野 信一/矢神 毅 訳 です。結構古い本です。
プログラム板的には「はじめての数論」も良いと思います。
プログラムを書く問題があったり、暗号についての話があったりします。
ただ証明は大体「数論入門I」のほうが分りやすかったです。

>>699
よく見たら、日付が1/8でした。
番号がそんなに違わないし、同じ話題が続いてるので、
少し前の公開かとカン違いしてました。

保守

保守

まだ改良頑張ってる人っている？

（　´∀｀）ノ

>>704 癌がれ。
じゃあ、当分は定期的に保守しておくよ。できれば途中経過など聞かせておくれ。

ウーン頑張ってもどうしても1億で1分4秒@pen2-350 Cygwinが限度でつ

http://members.tripod.co.jp/firstbornunicorn/prime.c
ダメだMAXが10^10を超えるあたりからcallocができないっす。
よってやめます。
メモリをケチることは重要っぽいです
1億くらいまでは正しく求められそうでした。

stdout だと遅いかと思われるのでリダイレクトして

#define MAX ???
に求めたい素数列の最大の値をいれてください

http://mathquest.com/discuss/sci.math/a/t/437162
ここに書いてあること分かる人いますか？
僕は英語苦手なのでよく分かんないんですけど、かなりレヴェル高い気がします。
あとdjb氏のより速いプログラム見つけた人いますか？
最近 primespeed で個数だけ数えてくれることに気づきました。

（＾＾）

http://www.google.co.jp/search?q=cache:lCAiHroWRnkC:mathforprofit.blogspot.com/+&hl=ja&ie=UTF-8
一応キャッシュ消えないうちに貼っときます。
とんでもなく速いですね。JAVAなのに。

http://ourworld.compuserve.com/homepages/hlifchitz/Homepage.htm
エラトステネスの計算量は O(n*log(n)) らしいのですが、O(n^(1/2)*log(n))
で計算できるらしいです。dvi ファイルに詳しく書いてあります(僕は理解して
いませんが)。
>>694 との関連はよく分りませぬ。

アドレス微妙に間違った。
Parity of pi(n) ってとこです。

nまでの素数を篩うんだったら、√nまでの素数を元にすればよくて、
これがループ回数を決定するから計算量はこの素数たちの個数で求まる。
で、素数定理よりその素数たちの個数が1/2 * n^(1/2) * log(n)個程度だから、

……でいいのかな？

>>713
今適当に考えてみたのですが単純にステップ数を数えると、
p <= √n 、 Σn/p ですよね。
Σ1/p <= log(√n) だから
O(n*log(n)) になるんじゃないのかな。

あ゛っ。そんな気がしてきた。
とりあえず>>711のソースを読んでみまつ。

http://seizen.gikoneko.net/~2ch/prime/
作ってみました。
ソース改良したり、アップしたり、リンク足したり、なにやってもよいと思いますが
いつ消えるか分りませんのでご注意。

>>711
の O(n^(1/2)*log(n)) で計算できるのは pi(n) の偶奇 ppi(n) らしいです。
ppi(n) + ppn(n-1) で n の素数性が分るみたいです。
一つの数の素数判定に O(n^(1/2)*log(n)) かかるので pi(n) を求めるには
O(n^(3/2)*log(n)) かかり、エラトステネスより効率悪いみたいですね。

保守。

　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
　　＝〔~∪￣￣〕
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉

保守アゲ
（盛り上げていこうぜ！！山崎渉なんかに負けんな〜）

パソコン買い換えて環境早くなったもんだから多少いじっても何も変わらん…

プッチ神父のスレはここですか？

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

磯引葦胃葦斡

>>722
すっかり落ち着いてますが

（＾＾）

よく分からんけど、とりあえず貼り
http://www.msnusers.com/AmateurMath/primecountingfunction.msnw

ちなみに PrimeCountH.java はくそ速いです。
今までの苦労はなんだったんだ ってくらい。

　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン

静岡、想い出登板ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!

n^p/p=x…n
n…適当な数　p…素数　

保守

保守

C++初心者ですが、この素数判定アルゴリズムはやはり低レベルでしょうか?

template<class T>
bool primality_test_1(T mainvalue)
{
//偶数を判別(奇素数判定ならこの部分はいらない)
if(mainvalue % 2 == 0 || mainvalue == 1)
return mainvalue == 2 ? true : false;
//事前条件: mainvalueは奇数 && mainvalue >= 3
T i = 3;
for(; mainvalue % i != 0; i += 2)
;
return i == mainvalue ? true : false;
}

mainvalueの平方根をとればもっと速さを短縮出来ると思ったのですが、
それをやると、第2forループの「番兵」が活かせなくなってしまうので、
何かよい方法はないかと思案しています

↑良い悪いはともかくとして、これより低レベルなアルゴリズムってあるかな？

>>735
偶数も含めて除算していくアルゴリズムが在るだろw


そろそろエラトステネスについては語りつくしたようだしテーマを変えてみないか?

次のテーマ "エラストテネスの篩い以外のアルゴリズムでどれだけ速くできるか?"

まずはウィルソンの定理あたりでw

判定スレ落ちてるので、こちらに書きます。

判定用アルゴリズムで、こういうの考えました。
多分速くは無いけど、メモリはそんなに使わないと思います。
2〜7の素数はデフォルトとして桁数が多い場合の処理を考えてみました。

たとえば８１３７の場合
もしこの数が素数でなければ、下１桁が１×７、または３×９の数字の積だと言うことがわかる。

そこで(１×７の計算は終わった物とします)
　　＿＿＿９
　３）　８１３７
　　　　　 ２７
　　　 ８１１
３と掛けて下一桁が１になるのは７だから

　　＿＿_７９
　３）　８１３７
　　　　　２３７
　　　　７９
３と掛けて下一桁が９になるのは３だから

　　＿___３７９
　３）　８１３７
　　　　１１３７
　　　　７
３と掛けて下一桁が７になるのは９だけど、３×９３７９はもとの数より大きいのでスキップ

つづく

つづき

　　＿___＿_９
１３）　８１３７
　　　　　１１７
　　　　８０２
と言う感じに計算すると、

　　　＿＿_７９
１０３）　８１３７
　　　　 ８１３７

となり、素数ではないことが分かる。
こんな感じで計算すれば、桁数が多くても網羅する範囲を絞れないでしょうか？

>>737　質問です
１３，１０３はどうやって決定するんですか？
１３，２３，３３，４３，５３…　って１０の位を増やして全て計算するんですか？

除算のみを使った列挙で1000万まで7秒ってどうですか?
(篩いなら一瞬だろうけど)

どんな環境で？

地球シミュレータ上で

　　 ／￣￣￣￣￣ ミ
　 /　　 ,――――-ミ
　/　　／　 ／　　 ＼ |
　|　 /　　　,（･）　（･） |
　 (6　　　　　　 つ　　|
　 |　　　　　　＿＿_　 |　　 ／￣￣￣￣￣￣￣￣￣￣
　 | 　　　　 /＿＿/ ／　 ＜　なわけねぇだろ！
／|　　　　　　　　 ／＼　　 ＼＿＿＿＿＿＿＿＿＿＿

n = (x * x + x + 1) / 4
sqrtを使わずにxについて解く事って出来ますか？

>>744
ニュートン法などによる近似

x^2 * 2 + x * 40 + 1
x^2 * 2 + x * 44 + 43
x^x * 2 + x * 48 + 89

>>739
レスきてた。

やっぱりそこですよね・・・。
それなら、判別する数の下一桁が１，３，７，９の場合、下１桁が１，３，７，９の数で順番に割ってみるっていう風にしたほうが早いですよね。

下一桁が０，２，４，６，８の場合は偶数、下一桁が５の場合は５の倍数なので判別する数が２桁以上の場合、必ず素数にはならないのですぐ結論が出るし。

下一桁が１の場合素数でなければ下一桁が１×１、３×７、９×９の合成数
下一桁が３の場合　〃　１×３、７×９　〃　
下一桁が７の場合　〃　１×７、３×９　〃　
下一桁が９の場合　〃　１×９、３×３、７×７　〃　

これをどうにか利用できないかなぁ・・・

>>747
とりあえず二進法で考えて下さい。
割り算がしたいのなら多倍長計算スレへ。

篩を使い、偶数のみ除いて
300万で30秒まで行きました。
まだまだ未熟者です。

リンクのソースを読もうと思ったら、
ほとんどリンク切れしてしまっていたのですが、
誰か早いのを作っている方で、
もう一度リンクを張っていただけないでしょうか？
できればCでお願いします。

>>426
>>617
>>727 はどっかいったみたい。ソース持ってるけど。

integer n > 1
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;
　2. r = 2;
　3. while(r < n) {
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;
　5. 　　if (r is prime)
　6. 　　　　let q be the largest prime factor of r - 1;
　7. 　　　　if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1(mod r) )
　8. 　　　　　　　break;
　9. 　　r = r + 1;
　10. }
　11. for a=1 to 2*aqrt(r)*log(n)
　12. 　　if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n) ) output COMPOSITE;
　13. output PRIME;

これって結局何だったの？

PrimeCountH はエラトステネスではないようなのですが誰か解説きぼん。

>>750
ありがとうございます

　　　　　　　　　　　　　_
　　（　　　　　　.，‐ '´ 　 ヽ-、_
　　　　　　 ／⌒）i　ﾚノﾉ）)） ＼ヾヽ　　　／￣￣￣￣
　　　　　／ヽ './人il.ﾟ - ﾟﾉｲ|/.ヾヾヽ＜　　みる、みる、みるまらーーー！
　ゞ　　 （"....（ (ヽ ⊂)Yiつヽ） |'ﾉ　　　　| 　わむてさん、地球！
　　　　　(" "ヽ＼.' く _ :|〉ヽ.ヽ| |　ノ　　|
　　　 　 　 '( " ヽ＼し'ﾉ　 ヽ| |ﾉ 　ノ 　 ＼＿＿＿＿
　 　（＼　　 　 '("ヽ＼　　 　 |ﾉ
　　　＼）　　　　　　 '(（. 　 　 "　　 し″

「4以上の全ての偶数は2つの素数の和であらわせる」
言数μの儀環δ(μ)によって外数μ'/偶数は定位を持つ。(自明)
線形乖離により轍環はδによる写像σの約値を持つ。
轍環は無限順列を持たない為、輪位は定位と双対ではない。(μ'までも乖離される。)
律価をοとすると言群をMとし、単置換をπとすると、約値が相似単置換π'に相当し
∀{∀(∀σ , ∃π) ,∃π' s.t δμ=φ},∃ ο∈NM s.t δπο∽σπ'μ が言える

これを展開すれば、言数定理によって、乖離され、
δπμ'=φ となる為、補遊値は0になる。
自然数においてδの域数 ω(δ)=2,
πの弄数 Å(π)=2 であり、 ω(δ)Å(π)=4
補遊値=0だから4+0=4。

∴4以上の全ての偶数は2つの素数の和で表せる

C初心者でこのスレの人たちには到底追いつけないのですが、
自分が発見した素数の定理を使用して素数列挙プログラムを作成しています。
それで、コンソールアプリケーションしか作れないのでそれでDOSに素数を表示してるのですが、
PCが計算して出した結果をDOSが表示するのに追いつきません。
このような場合は表示を省いてもいいのでしょうか？

また、計算を始めてから結果を出すまでの時間はどうやればよいのでしょうか？
よろしくお願いします。

>>756
コンソールに出さずにファイルに出せばいい

>>757
それでやってみました
時間の問題は他人のソースをパクって解決しました。
で、結果ですが10億までの素数ならcele700で18秒でした
もっとプログラムの勉強をすれば短縮できそうです。

10億で18秒って鬼だと思うんですが

出力して18秒なら鬼

>>758
まさかと思うがラビンテストでやってないよな？

本当に18秒台です。C言語で。
ただ、ファイルには出力せず、DOSに一部を表示してるだけですが。
もちろん表示してるのは少なくてもしっかり全部計算してます。
また、この定理をコンピューターで使用すると
今までのように素数の桁が大きければ大きいほど加速度的に計算時間が伸びるようなことはなく、
少ない桁のときより少し大きいだけで済むと思われます。

100億とかも調べたいのですが、unsigned long intでも40億程度までしか調べられないんですね・・・。

>表示してるのは少なくてもしっかり全部計算してます。
なんだよ。神が降臨したかと思ったじゃねーか。

>>762
割と最近発見された，多項式時間で素数／合成数を判定するアルゴリズムは
係数部分が馬鹿でかいと聞いたがな…

>>762
決定的多項式時間で素数判定するAKSアルゴリズムは
桁数の12乗のオーダーだそうだ

>>763
ｽﾏｿ・・・　表示するだけとしてはまだまだ遅いんですか？

>>764
自分はそれほど詳しくないしC言語も初心者レベルなんですけど
素数列挙って面白いですね。
AKSアルゴリズム、いつかは自分で理解できるぐらいになりたいです。

十億で18秒って早くないか？


ん・・・俺が無知なのか？

>>767
http://www.google.com/search?q=Mathematica+prime+10%89%AD&num=50&hl=ja&ie=Shift_JIS&c2coff=1
http://www.vector.co.jp/soft/win95/edu/se221945.html
上には上ｇ（ｒｙ

>>768
上の１８秒はCeleron700なので，こっちのが速そうだ

一度全く同じ環境で試して欲しいもんだ
つーか、>>764はさっさとその定理を証明して発表汁。
そうすればもしかしたら素数アルゴリズムブームが起きるかも試練

だからさぁ、>>762は全部表示していないという時点で終了

ファイルに出力してみろってんだ

列挙型じゃないけども
p=2*3*5*7*11*13*17*19・・・　+1
素数を順番にかけていって最後に1を足せば必ずpは素数ってのを利用して
世界一大きな素数を発見ってできるかね？
これだと結構大きな素数発見できるはずだけど
素数をあらかじめ順番に大量に並べておかないといけないから前処理が大変。
目指せ100万桁ってのは無理かな、無理だね。

>>773
>素数を順番にかけていって最後に1を足せば必ずpは素数

電波は混乱のもとになるので帰ってくれ
2*3*5*7*11*13*17*19+1 = 9699691 = 347*27953


何の確証もない仮説を書き込む前に一つくらい試してみろよと言いたい

合成数を並べて階差をとっていくと・・・
━━━━━━(ﾟ∀ﾟ)━━━━━━・・・（´･ω･｀）

>>773 >>774
なるほど初めて気づいた

確かによく考えると
「素数が無限に存在する」ことを証明するこの論法は
素数が有限という「誤った仮定」を利用して
全ての素数（実際は無限に存在するが）を掛けて 1 足すと素数…
とやっているわけだから
無限に存在する素数のうちの有限個を掛けて 1 足す
で成り立つかどうかは分からないんだよな

実際 >>774 が反例を示してくれているし

>>774
手計算ではしんどいからやらないが、
2*3*...*p+1
と 2..p の全ての素数を掛けて 1 足した数が合成数となる最小の素数 p は何？
19 より小さい p はある？

ただ、大きい素数は抽出できるが素数列挙には向かないな。

自分でやってみた

2 * 3 * 5 * 7 * 11 * 13 + 1 = 59 * 509

13 か…人に説明するネタに使えそう

10億18秒って速くないか？
桁数が上がっても加速度的に計算量が増えないって言うし。
本当なの？

訂正。桁数が上がっても加速度的に計算量が増えないって本当？

どうでもいいから PrimeCountH を解読すれ。

$i=2;
print "$i\n";
$s='o' x $i;
$pattern="($s)*";
while(1){
 $s=$s.'o';$i++;
 #print "s=$s\n";
 if ($s!~/^$pattern$/){
  print "$i\n";
  $pattern=$pattern.'$|^('.'o' x $i.')*';
  #print "$pattern";
 }
 #getc;
}

>>783
Cygwin で実行すると 256 の壁に当たったようで
258 番目の素数として 1622 とか出力してるな

primes = 2 : sieve [3, 5..] where
　　　　　　　 sieve (p:xs) = p : sieve[ n | n <- xs, n `mod` p /= 0]

>>784
ActivePerlでも1600超えると落ちました
正規表現が大きくなりすぎるのかも
正規表現雑技のページを見て割り算とか篩とか
使わずにやってみたくなったんだけど
シンプルじゃないうえに欠陥品でちょっとガッカリ

結局現段階で一番早いのは誰のソースですか？
できればそのソースも見たいです。

私が1ヶ月前にこのスレを発見していろんな意見を参考にして作ったのとどっちが早いか勝負してみたいです。
ファイル出力はしなくてもOK、時間表示が出ていればOK

最速ではないが、とりあえずこれと比べてみれ
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

だから PrimeCountH だっつーの。ググれ。

>>789
数えるだけじゃダメだろ

>>790
そっか、数えるだけじゃダメか。
数えるのも一個一個値出すのも一緒じゃんって思ったけど、
PrimeCountH はエラトステネスじゃないから違うのかな。
数える速さはだんとつで速いと思う。

>>791
エラトステネス使ってるだろ。

>>792
それはルートNまでの素数を計算してるだけでは?

>>793
そうだけど、それが何か？

>>794
だから核となるアルゴリズムはエラトステネスじゃないってことだよ。
あたまだいじょうぶ？

>>795
ﾊｧ?
素数 "列挙" できるのはそこまでだろ？
スレタイちゃんと読んで出直せ。

>>796
だから >>791 の発言につながるわけですが...

どこかのスレで「参考になるループ発言」にでも使われるのだろうか。
見事すぎる。

負けました。
出直してきます。

ん〜〜〜〜〜。なんか、既存のソースの検証ばっかになってない？
クリエイティブにいこうぜ！！

既存のソースの検証をせずにクリエイティブな仕事のできる天才はどこですか。
そもそも素数列挙ってアルゴリズムはエラトステネス一択だし、
素数判定や素因数分解みたいな高尚なテーマに比べるとずーっと奥が浅い。
素数カウントはそれなりに難しいのかもしれない(おれは分からない)。
pi(x) project ていうのあるしね。

解析数論の進展により，初等的ではない新しいふるい法が開発されて
素数列挙がさらに高速化するという可能性は無いのか

無いことを証明するのは難しいな

「素数定理を初等的に証明せよ」

まず素数定理とは何だ？

あれだ
ガウスが15歳の時に思いついたけどガウスにとっては初等的過ぎて証明しなかったやつ
その後誰かが手柄横取りした

初等的の意味分かってるのかと

>>806=初等的=簡単と思ってるアフォ

http://www.google.com/search?num=50&hl=ja&inlang=ja&ie=Shift_JIS&q=%8F%89%93%99%93I%82%C6%82%CD&btnG=Google+%8C%9F%8D%F5&lr=lang_ja

保守

http://news5.2ch.net/test/read.cgi/newsplus/1070452163/

俺はものすごいアルゴリズムを考え付いたが、
多分このスレでも既出だろうし、なにより余白が少ないので
保守だけさせてもらいます。

保守が必要だと思うなら発表してこのスレに命を吹き込んでくれ
期待はしてないよ。

既出「だろう」し、ということは「読んでません」と言ってるようなもの。
他人の意見に興味を示さない人に大したことができるとは思わない。