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

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/

俺はものすごいアルゴリズムを考え付いたが、
多分このスレでも既出だろうし、なにより余白が少ないので
保守だけさせてもらいます。

保守が必要だと思うなら発表してこのスレに命を吹き込んでくれ
期待はしてないよ。

既出「だろう」し、ということは「読んでません」と言ってるようなもの。
他人の意見に興味を示さない人に大したことができるとは思わない。

>>813
812は、フェルマーのパロディだろ。

もう素数列挙は限界みたいなので素数カウントに興味が移り始めたのですが、
おもしろいページを発見しました。PrimeCountHなんかもこの計算方法を使ってるんでしょうね。
http://mathworld.wolfram.com/PrimeCountingFunction.html

はっきり言って、このスレはすごい。
2ちゃんねるでやるにはもったいない。

どこでやるなら良いのかと。

>>817
ドトール

アスキーから出版されてるプログラミング作法、このP68の問2-4解けるかたいませんか？

問題概要：n個の数列をできる限り低速にソートするアルゴリズムを設計実装せよ。
インチキな実装はしてはならない。
そして、そのアルゴリズムの計算量はいくつか？

問題の意図はおそらくO(n^2)よりも遅いソートアルゴリズムを見つけよだと思うのですが…
お知恵を貸してもらえませんか？
お願いします。

あっ、すいません。
スレ違いでした。
無視してください。

どこらへんがすごいんだよ。

保守

正直な話
素数さんと結婚するにはどうしたらいいですか？

>>823
子供を産んで、「素数」と名づけるほうが現実的。

このスレって人いたんだな
ずっと放置かって
わびしさを感じようと思ってたんだけどな

そりゃageればな

>>826
定期的にチェックしてるのかよ！！！

>>827
バカなの？

いやいや
>>823は確かにageたんだけどさ
>>825はageてないだろ

なのに半日もたたないうちに
>>826のレスがあったから
>>826は定期的にチェックしてるのかよ！！！
っていうレスを>>827でしたわけ

>>829
2chブラウザのスレ一覧を最終取得日時か最終書き込み日時でソートしてれば
最近レスしたスレにレスがあればすぐ見ることができるでしょ？
本人じゃないから分からんが別に定期的にチェックしてたのとは違うと思うよ。

ひまだのう
このスレ見てる椰子は
手を上げて
ﾉｼ

ノ

(@�u@ .:;)ﾉｼ

ﾉｼ

ﾉｼ

おい、今二回手を上げたやついただろ

素因数分解してみたまへ
68228966604347

普通に割り算したらできたけど。
9333113 7310419

>>838
(　´･∀･`)へｰ

28347681350622442076102437227047036279370375374966
02761076051676968780023033056412274753966959194281
23826876790980636135577027355018080405658377196148
25204708757084342552431413687656764459968946860901

これはどうだ
200桁の合成数です
一行50桁となっております。

2 43 179 55213 33352217547282731980572401063704197838103
7 7 10993 271553 18876064647159886325909391381305666761
2 2 3 1433 18205739579 76108183479522373499388340361881397
246512013571 1157771962604483 88312171996847023952957
それ以上は聞かないで...

ここは暇なインターネットでつね

200桁は無理だよ。

やっぱそうですかね
どなたかRSA暗号で平文を暗号化して
公開鍵を公開してこの暗号を解いてみろとやってみてくださいな

>>843
完全にスレ違い
専用スレでも立てれば？
ただし他の(暗号解読の話題に一番適した)板で

http://primes.dnip.net/primes_1_1.tar.gz
昔作ったやつを改造してみますた。
計算量増えてるけどメモリ効率は良くなってるので、一兆くらいまで計算すると前のより早くなるはず。

10兆とか100兆までの素数すべてを記録しておくことなどできっこない。
かといってメモリ回すだけじゃ意味ないから素数の個数を出力するようにしたんだけど、
数えるだけならもっと速いアルゴリズムがある。
エラトステネスのふるいに価値があるとしたら、ある範囲(結構広め)の素数を探すとか特殊な素数(双子素数とか)を探すとか
になってくると思う。

>>845
どこのへんの人だい？
すっかりさびれちまっててすまねぇなぁ

100兆まで計算させてて320時間くらいたって、あとちょっとで計算終わりそうって時に
東京電力の検査が来ました (⊃д`)

>>846
621とか396とからへんの人です。あんまりネタないですからね。

昔、N以下の素数をあらかじめ省いて計算するプログラムを書こうと思って、
プログラムを書くプログラムを作って巨大な switch文を生成したことがあります。
すごくコンパイル時間がかかって、バイナリがでかくなって、ちょっとだけ速くなった
とかいう感じでした。
今なら C++で書けばすっきりしそうな気がします(相当マニアックなことしないといけませんが)。
すごくやりがいはありそうなんですが、なかなか暇がないです...

>>847
C++使えば確かにすっきりはすると思うけど、
それに伴い速度が、落ちると思うよ…

>>848
いくつかの素数の倍数を省いたエラトステネスをを素直に実装すると割り算が必要になってきます。
でもそれは、あらかじめ差分を計算しておくというテクニック(>>331)て回避できます。
素数候補の数も変わってくるので場合分けの数も変わってきます。
こういったメタプログラミングをするのに C++の templateが有効だろうと思ったんです。

でも結構大変で本当に実現できるかどうか分かりません。
あと、思ったより templateの展開が遅いです。11まで省くのは無理かもしれません。
コンパイル時にエラトステネスで素数計算させてみると、100までで7秒くらいなのに200までだと1分以上
かかったりします。
正直 templateのことはまだよくわからないです。

>>849
なるほどね
でも、実行時の速度を考えるならテンプレートを作るよりも
Cのソース(の一部)を吐き出すプログラムを作った方が速くなりそうな気がする
テンプレートって色々出来るけど、実行時の処理が重くなる時が多いので…
まぁ、使い方にもよるし、上手く使えれば、そんな事ないかも知れないけど…

>>850
その通りですね。
ソースをべたべた張りつけるような用途にTemplateは向いてないみたいです。
inline展開を信用すれば同じことができるんですけど。
とりあえず文字列レベルのマクロで十分なのでm4というのを使ってます。
クォートだらけでわけわからないですけど、まあ意図通りに展開されるのでいいかなあと。
肝心のプログラムはなかなか意図通りに動かないです。
コンパイルに10分以上かかってめんどくさいし。ほんとに速くなるのかな?

なんとか苦労して7の倍数まで省いて計算するコードをm4で生成しました。
ソースコードは3M弱、実行コードは800Kくらいで、計算結果も正しいものに
なったのですが速度は遅くなりました。やっぱり5の倍数までがちょうどいいみたいです。

自分のより速いのも見つからない上に、たいしたテクニックを使ってないというのもあり
またエラトステネスの意義自体微妙なのでとりあえず終わりにします。
>>694 の Pnをを求めるっていうのも適当に当たりつけてカウントしてからふるった方が
速いんじゃないかって気がします。適当ですが。

50桁の問題４つじゃなくて２００桁の問題だろう。

何となく

age

大地震翌日age

個人的に良スレだから保守しておきます。

現状（Pen4 2.4G)
1億までの列挙に 9 sec
10億までの列挙に 102　sec
列挙先はファイル

10億で18秒か…、先はなげー

とりあえずエラトステネスのふるいのまとめ。
そんな奥の深いアルゴリズムではないのでやれることは限られてます。
1. ふるいをビットで保持
2. 小さな素数をあらかじめ省いておく(おそらく 2,3,5までが最良)
3. 2.によって生じるビットの位置を求める計算を割り算ではなく場合分けで行う
4. ふるいを分割する
僕の知ってる限りではこのくらいです。

あと、
5. 小さな素数(7,11,13,17)の積の大きさのふるいをあらかじめ作っておいて、
それをコピーすることで、それらの素数でふるうための計算を省く
というのもあります。泥くさいですが、意外と効果があります。

1,2,3については >>428にまとまってます。あとはふるいの分割ですが、これによって
3がちょっとだけ複雑になります。
ビットカウントにHacker's Delight方式を使うなど細かいことはありますが
おおむねのアルゴリズムはこんなもんです。

そんなエラトステネスのふるいの計算量のオーダーは O(NlogN)ですが
もっとオーダーの良いアルゴリズムがあるようです。

http://cr.yp.to/ntheory.html#primesieves
計算量のオーダーは O(N/loglogN)らしいです。

暗号なんかで使う素数を作る時には
素数候補に対して2000以下の素数で割ると
前処理の効率が一番いいんだけどな。

今現在で
CPU 2.0GHz
MEM 1GB

のPCを1000台使って並列処理させて
ビット数が等しい素数p,qの積n(256bit)を
素因数分解しようとしたらどれくらいの時間が掛かりますか？

本日の状況
1億までの列挙に 5.313 sec
10億までの列挙に 56.703 sec

>>859, 860, 861
ありがと （まだコードに落とせてないのもあるけど）

>>862
p,qの性質によるだろ。例えば、p.qが双子素数なら、一瞬で終わる罠。

>>864
(　´･∀･`)へｰﾍｰ(´ν_.｀　)ｿｳﾅﾝﾀﾞ

1億　2.25sec
10億　28.609sec

ファイルへの出力方法かえたら半分くらいの時間になった

大きく変わったね。

本日は大きな進歩なし　行き詰まりぎみ
気分転換に860のアルゴリズムで作ってみた
結果は1億桁で 5.186sec
現状、エラトステネスより遅いけど、
いいかげんに作ったプログラムなので仕方ない
明日はもうちょっと作りこんでみる

>>862
さてはRSALabの因数分解問題を解いて賞金をゲットしようという魂胆だな

>>870
違うよん

本日も進歩なし
新しいコードに列挙漏れが発覚
実装ミス

2,3,5の倍数を除き、1バイトに8個詰めることにより、
30*2^32（1280億）まで拡張可能なコードを書いたが、
1億までのビット計算に4.3s、ファイル出力にさらに7.5s
10億までだと、ビット計算に56.1s、ファイル出力にさらに72.6s
これだと、100億までやると、
メモリ512MB、出力ファイルサイズ5GB、総時間40分くらいかかりそうだ。

本日も進歩なし
双曲線の漸近線がよく分からん
アルゴリズムの意図しているものが
本当に漸近線なのかもよく分からん

>>873さんの書き込みで気づいた
２，３，５の倍数を除くってのは
はじめからそれ用のバッファを持たないってことなのね…
すげー勘違いしてた　初期化のときにそいつらだけ０で消すってことなんだと思ってた…
確かにこうしたほうが効率よさそう

一応、僕がエラトステネスやってて思ったことを。
・素数は 6*i+1 6*i+5 にしかないのでそこ以外見ない （>>311)
・なんでか知らんけどｘ／32という計算のほうがx>>5よりも速い（僕の環境では）
・出力はバイナリ出力でwrite関数とか使うと速い（列挙とはちょっと意味が違うけど）

874のレベルがとても低いことが分かった。
ようやく言える。日記はチラシの裏にでも書いてろ。

>>873
ファイル出力遅すぎじゃないか？

for(Loop=0;Loop<Max;Loop++)
{
　　　　if(X[Loop]!=255)
　　　　{
　　　　　　　　if((X[Loop]&128)==0)fprintf(fp,"%d\n",30*Loop+7);
　　　　　　　　if((X[Loop]&64)==0) fprintf(fp,"%d\n",30*Loop+11);
　　　　　　　　if((X[Loop]&32)==0) fprintf(fp,"%d\n",30*Loop+13);
　　　　　　　　if((X[Loop]&16)==0) fprintf(fp,"%d\n",30*Loop+17);
　　　　　　　　if((X[Loop]&8)==0)　fprintf(fp,"%d\n",30*Loop+19);
　　　　　　　　if((X[Loop]&4)==0)　fprintf(fp,"%d\n",30*Loop+23);
　　　　　　　　if((X[Loop]&2)==0)　fprintf(fp,"%d\n",30*Loop+29);
　　　　　　　　if((X[Loop]&1)==0)　fprintf(fp,"%d\n",30*Loop+31);
　　　　}
}
現在のファイル出力部分のコードです。

そりゃ遅いわ。ビット計算はそれなりなのに勿体無い

873さんのを取り入れた結果（VCでコンパイル）
１億　1.859sec
１０億　23.5sec

いまいち自分の実力が分からんから
前にやってた人と環境をあわせようと思って
cygwin g++ -O3でコンパイルしたら
１億　1.281sec
１０億　17.859sec
（ただしファイル出力はバイナリ）

VCで最適化かけたほうが速いもんだと思ってたんだけど…そういうわけじゃないのね

速度的にもアルゴリズム的にも見るべきところが無いのだから、
そんな書き込みでスレを荒らさないでくれ。ここは日記帳じゃないんだ。

日記帳というか便所の落書きじゃなかったか？

でも日記でも落書きでも僕が書いたから
ほかの人もやり始めてくれたんじゃないの？
わかんないけどさ。
ボーっと見てれば
レベルの高い人が見所のあるプログラムを書いてくれるとでも思っているの？
お前ら、すごい人のおこぼれ欲しがってるだけじゃん。
惰性で生きてる人間がモラルなんか持ち出すな。
しょうもない

>>879
君は最近やり始めて新鮮なのかもしれないが、このスレにとってはなんの価値もない。
本来なら「過去ログ嫁ｳﾞｫｹ」と一蹴されるはずの内容なんだよ。
荒らし以外のなにものでもないよ。882の書き込みにはある種、感動したけどね。

・ちまちま書き込まない（ある程度溜めてから一気に書き込む）
・30*Loopは変数で保持

このスレ自体には何か価値あるか？

とりあえず名無しで実行時間書くならそのつど、CPU,Memoryは最低限書くべきだと思うのだが…
でないと比較のしようがないと思うのは私だけ？
OS,コンパイラ,コンパイルオプションまで有ればなお良しということで

>>882-883
このレビューは参考になりましたか？
◎はい　○いいえ

Pentium4 2.40GHz メモリ256MB VC++ 6.0
1億まで　6.2秒（テキスト形式でファイルに出力）

2と3の倍数を除いてる。6秒切れない…

わーい、爆速コードの進捗状況と新しいアルゴリズム教えてもらえて嬉しいな
明日もよろしくね

Pentium4 2.40GHz　メモリ512MB　VC++6.0
テキストで出力すると1億まで　8.843秒（前のはバイナリで出してた）
あぁ、レベル低いって言われてもしゃあないなぁ…

890氏のは2､3､5の倍数のみ省いたものなのかな？

？？？

エラトステネスの篩。2と3をとばしてある。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1035246186_13/hurui.cpp

% g++ -O3 -o hurui hurui.cpp
% time ./hurui 100000000 > primes
32.870u 0.800s 0:35.75 94.1% 0+0k 1+14io 0pf+0w

環境
MacOS X 10.3.6
PowerMac G4 Cube 1.2GHz( Upgraded ), memory:832MB

35秒か...
>>890の足下にも及ばんな...

っていうかおまいら、
>>879　一億で1.8秒？！！！！
しかも >>880　速度的に陳腐なの？


...すまん...出直してくる...
つか、どんなアルゴリズムだ...

...λ.......

っていうか、10億なんて

% time ./hurui 1000000000 > primes
349.720u 7.230s 6:17.60 94.5% 0+0k 35+88io 0pf+0w

6分ですよ、６分。
PowerPCが悪いの？んなわけないよな。

だれか、
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1035246186_13/hurui.cpp
の、糞な部分を指摘キボン....

>>895
多分ストリームを使わずprintfにするだけで
かなり縮むと思うぞ。

>>896
それがですな...
std::coutを使用せずに、
カウンタのインクリメントに置き換えてみたんですわ。

そしたら、速度が3倍になりました。

３倍。
たかだか３倍。
18秒なんて、夢のまた夢

入出力に時間が掛かっても大した問題じゃないだろうに。

入出力はスレッドでキュ

はっきり言うと、相手にするやつが悪い。

はぁ？

こんなことになるくらいならさっさと落ちたほうが良かったよ。

>>895
＞ inline static prime_t getIndex( prime_t prime ) {
＞　　　　　return ( ( prime / 6 ) << 1 ) + ( ( prime % 6 ) == 1 );
＞ }
これが最大のボトルネックだろうなぁ…

＞ if( i < checkLimit2 && table.check( i += 2 ) ) {
テーブルのサイズを1つ多めに確保しといて、 6i+1 を列挙しなくていい
時はそのビットは立てないようにする。そうすれば i < checkLimit2 はいらない。

>>903
指摘ありがとう。....そうだな。
getIndex()は、確かにボトルネックだな。
探索する空間の広さに比例(いや、n log nか？)して呼び出されるし、
割り算を2回も行っている。

２個めのパラグラフは全然判らん。
テーブルのサイズを一つ多めに確保しておいて、
6i+1を列挙しなくていい時はそのビットを立てない？
....orz...すまねぇ、ほんとにわからねぇ....


>>896
やってみました。すげー。びっくりした。
time ./hurui2 100000000 > primes
11.250u 0.550s 0:12.54 94.0% 0+0k 0+18io 0pf+0w
カウンタをインクリメントするのとかわんねーな。
激速。ただ...1億1.8秒には、全くかなわないけど。

で、いろいろやってみた。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1035246186_14/hurui2.cpp
なんだかすっきりしたが、

>>903
に指摘されたような問題は解決されていない。

% time ./hurui2 1000000000 > primes
135.490u 6.520s 2:32.30 93.2% 0+0k 24+41io 0pf+0w

10億で2分半。18秒？ハハッ！

>>905
コードや環境の違いがあるから一概には言えないかもしれないけど、
check()内で素数を見つけながら出力するより初段ループで篩い分け、
次段のループでテーブル走査の方が早い気がする。
昔書いたコードでは後者の方が早かった（数が大きくなれば逆転するかも）。

for(i=1; i+i+3<=√MAX; i+=3){
　　i+i+3とi+i+5をチェック、篩い分け
}

for(i=1; i<=テーブルのサイズ; i+=3){
　　i+i+3とi+i+5をチェック、出力
}

素数列挙と素数判定はどちらが難しいですか？

素数を列挙するためには素数かどうか判定しなきゃいけないと思うのは漏れだけですか

>>908
その必要はない。
ごく簡単なアルゴリズム、例えばエラトステネスのふるい法を考えても、
一つ一つの数が素数かどうか判定していないでしょ。

そういやそうですな

Nまでの素数列挙とNの素数判定だったら後者は前者に含まれてる。
Nまでの素数列挙とN^2くらいの大きさの数の素因数分解だと後者の方が簡単だと思う。
少なくとも素数列挙できるレベルのNに関しては。

篩処理と表示を分離したらバナナ問題が発生してしまった。

読めない

篩部分を別スレッドにしようとして頓挫

古い篩

篩マーケット

篩発売中

どのhurui.cppかわからんが23行目でnew[]やったきりdelete[]してないな。

それ俺だ。
しばらく仕事でJavaばっかりだったからうっかりしてたのさ。
その点は修正済み。

これを観てアプリケーション終了時に
deleteすべきかどうかについて興味を持った人は、
よそで議論を。

俺の中で最新の篩。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/33.txt
(ファイルの拡張子がTXTなのは見逃して、UPLOADERの制限なんだ)

% time ./furui3 100000000 > prime_list
9.350u 0.480s 0:10.41 94.4% 0+0k 1+3io 0pf+0w
だいたい１億までの列挙に10.5秒。

% time ./furui3 1000000000 > prime_list
118.680u 6.060s 2:15.84 91.8% 0+0k 15+30io 0pf+0w
10億だと2分16秒か。

MacOS X 10.3 / PowerMac G4Cube
PowerPC 1.25GHz / mem:0.8GB / BaseClock:100MHz

くふう
1. 篩処理と表示処理を分離した
2. いままでは「上限値を超えない」範囲でループを回していたが、
　あらかじめループ回数を計算して、その回数だけ、ループを実行するようにした。
　これによりfor( i = 1; i < [固定値]; i+=[固定値] )という、
　多分一番最適化しやすいループになった。
　(前のは for( i = 5; i < [固定値]; i+=[可変値]) )
　ほんとに最適化しやすいのかどうかは知らない。
3. 2により、「整数」の世界と「6n+1/6n+5」の世界の間の
　数値の変換が減った。
4. 表示にprintfを使わないようにして、
　文字列表示用のクラスを導入した。1億までで、4秒くらい稼いだ
5. 今までは、素数を見つけたあと、その素数の倍数にmarkする処理の
　ための増分値の基底として「見つけた素数の6倍」の値を使っていたが、
　これを「見つけた素数の４倍」と「見つけた素数の2倍」の両値の
　排他的論理和を使う事にした。
　これで探索可能範囲が61ビットから62ビットまで増えた
6. 素数そのものを示すためのprime_tと、配列の添字の為の
　index_tを明確に分離した。
　

で、改善したいポイントが一つ。

えっと、整数ををp(n,i)の形で表す事にしたんだ。

p(n,b)を、通常の整数に直すには6*n + b * 4 + 1とする。(nは整数、bは0か1)
これだと、6n+1と6n+5しか表現できないが、
2と3を除く素数は必ず6n+1か6n+5だから、これで充分。

んで、整数からp(n,b)の形に変換する処理には
n = 整数値 / 6
b = 整数値 % 6 == 5
と、2回の割り算が必要になっている。

この、整数からp(n,b)に変換する処理を行わないようにしたい。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/33.txt
のコードで言うと、PRIME_TO_INDEXマクロを、呼ばなくていいようにしたい。

どうすればPRIME_TO_INDEXマクロを呼ばなくていいようになるかと言うと、
p(n,b)の値の5倍、7倍、11倍、13倍、17倍、19倍...の値を
簡単に見つける方法があればいい。

今はどうしているかと言うと
1. p(n,b)で表現された整数値（Iとする）を得る。
2. Iの4倍値 inc4とIの２倍値inc2を用意する
3. Iにinc4を加え、あらたなIとする
4. Iをp(n,b)に変換する
5. その値を使って、処理を行う
6. Iにinc2を加え、あらたなIとする
7. Iをp(n,b)に変換する
8. その値を使って、処理を行う
9. 3にもどる

と、このようにしている。
これはFurui#goの、２個めのforの内容だ。

どのようにしたいかと言うと
1. c = 5,7,11,13,17,19,21,...と続くループを用意する
2. p(n,b)のc倍の値のp(n,b)表現を得る
3. それを処理する
具体的には、こんな感じ。

int c = 5, p, inc = 4;
while( p = multi( prime, c ), p < maxTimes )
　　mark( p );
　　c += ( inc ^= 0x06 );
}

過去ログ読まないの？
読んだ上で低レベルな話してるの？
発言するより、過去ログ読んだり人のコード見たりしたほうがいいよ。

正直ループ内で割り算を使う理由がわからない。2と3の倍数を除く基本アルゴリズムはこうでしょ。
6n-1のn=1でふるう。
(6n-1)(6n+1)=6(6n^2)-1
(6n-1)(6n-1)=6(6n^2-2n)+1
よって、6n-1側は、6個目から5個おきにふるう。
6n+1側は、4個目から、5個おきにふるう。
6n+1のn=1でふるう。
(6n+1)(6n+5)=6(6n^2+6n+1)-1
(6n+1)(6n+1)=6(6n^2+2n)+1
よって、6n-1側は、13個目から7個おきにふるう。
6n+1側は、8個目から、7個おきにふるう。
n=2では、
6n-1側を、6*2^2=24個目から11個おきにふるう。
6n+1側は、6*2^2-2*2=20個目から、11個おきにふるう。
6n-1側を、6*2^2+6*2+1＝=37個目から13個おきにふるう。
6n+1側は、6*2^2+2*2=28個目から、13個おきにふるう。

これより速いやつあるぅ。

printf("2, 3, 5, 7, ..................., ->∞\n");

メモリが有限なので実行できません。

>>924
見たけど、よくわかんねーんだよ

>>925
ループの中で割り算を使うのは、
素数を(n,m)(ただし素数=6n+4m+1とする)に変換する処理で必要だから。
素数pをみつけたら、5p,7p,11p,13p...をマークしなきゃならないし、
その為にはpに4pを足し込み、つぎに2pを足し込み...と続けなきゃならない。
これを(n,m)の世界だけでは、俺は処理できなかったんだ。

で、>>925の書き込みを見ても何の事だかさっぱり判らなかったんだが、
「素数pを見つけたときに、マークできる(ふるう事が出来る？)数字と
それの(n,m)表現」
を、5,7,11,13,17,19について、10個づつくらいあげてみて、その法則性から
(n,m)表現だけで、マークするポイントを探す事が出来るようになった。

そしたら >>925 のあげてるのと同じになった。
俺、理解していないのに。なんか不思議。

で、これがそれ。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/40.txt

% time ./furui5 100000000 > prime_list5
7.810u 0.580s 0:09.06 92.6% 0+0k 0+7io 0pf+0w
1億までで9秒ちょい

% time ./furui5 1000000000 > prime_list5
106.520u 5.870s 2:01.07 92.8% 0+0k 29+45io 0pf+0w
10億で121秒。

目標あと５倍。

もうちょっと改良。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/46.txt
素数を見つけたあとの、その素数の倍数をふるい落とす時の
ループを単純な感じにした。

% time ./furui6 100000000 > prime_list6
7.940u 0.590s 0:08.92 95.6% 0+0k 1+7io 0pf+0w
1億でギリギリ９秒を切った。

% time ./furui6 1000000000 > prime_list6
105.110u 5.980s 1:59.37 93.0% 0+0k 19+40io 0pf+0w
10億でも、やはりぎりぎり2分を切った。

PowerPCG4 1.25GHz(G4Cube Upgraded)
メモリ: 832MHz
MacOS X 10.3.7

正直もういいから
な！930

>>931
ここは広告の裏だ。

な？わかるか？

まだまだ改良の余地あり。

1億まで（ファイル出力なし） Pen4 2.4GHz WinXP
>>930（+puts部分コメントアウト）
…7.06秒
漏れのソース
…6.42秒

# OperaとかUDとか起動しまくり状態。

このスレってネタがネタだけにリアル中高生が多い予感。

>>932
>>930で９秒切れるんなら>>929でも切れるんじゃないか？

go( )の中の i のループも工夫できそうだね

#include <stdio.h>
#include <stdlib.h>

void PutsInt(unsigned int n){
  static unsigned int len;
  static char buf[20];
  static unsigned int p;
  unsigned int u;
  int i;

  u = n - p;
  p = n;
  for(i = 0; u > 0; i++){
    u += buf[i];
    buf[i] = u % 10;
    u /= 10;
  }
  if(i > len) len = i;
  for(i = len - 1; i >= 0; i--){
    putchar('0' + buf[i]);
  }
  putchar('\n');
}

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 * PrintPrime( unsigned int nn )
{
const n = nn - (nn % 6 == 0 || nn % 6 == 5 ? (nn + 1) % 6 : nn % 6 - 1);
const MAX3=(n+2)/3;
unsigned char * tbl = malloc(MAX3);
unsigned int m=1,n1,n2, x;
 memset(tbl,0,MAX3);

 while (m < MAX3){
  if(!TestBits(tbl, m) ){
   x = m*(3*m+4)+1;
   n2 = 6*m+4;
   n1 = 2*m+1;
   PutsInt(3*m+2);
   while( x<MAX3){SetBit(tbl, x); if(x+n1>=MAX3) break; SetBit(tbl, x+n1); x += n2;}
  } m++;
if(m >= MAX3) break;
  if(!TestBits(tbl, m) ){
   x = m*(3*m+2);
   n2 = 6*m+2;
   n1 = 4*m+1;
   PutsInt(3*m+1);
   while( x<MAX3){SetBit(tbl,x); if(x+n1>=MAX3) break; SetBit(tbl,x+n1);x+=n2;}
  } m++;
 }

 return tbl;
}

int main(int argc, char *argv[]){
  if(argc != 2) return 1;
  PrintPrime(atoi(argv[1]));
  return 0;
}

428を改造したコードだよ。君のと比べてみ。
君みたいな厨が現われないように859を書いたんだよ。
今となってはこのスレ、落とすのも埋めるのも変わらないかもね。

あ、桁溢れ忘れてた。
whileの条件の中は m < sqrt(MAX3/3) で、抜けたあとに
 for(; m < MAX3; m++)
   if(!TestBits(tbl, m))
     PutsInt(m);
て感じで。
mallocの中はMAX3/7くらいで。

>>875
>>880
>>883
>>92
>>931
同一人物かどうか知らないが、お前(ら)が一番邪魔。

>>92 --> >>924

教えてくれ、悪意のないバカが日記を書き始めたらどうしたらいい。
君は頭なでなでして飴玉あげたいのかい？ 俺にそんな母性本能はないよ。
そうなんないように早めに「最低428」ってハードルを作っといたんだよ。
そしたら平気でそのハードルくぐってきやがった(笑い)。
まあ、こういうのも含めて2ちゃんねるなわけだが。
もういいよ、止めないから埋めてくれ。

悔しい。>>939に500ﾐﾘ秒負けてしまった。

>>943
悪意の無い馬鹿が日記を書き始めたらどうしたらいいって？
放置すりゃいいんじゃね？

２年後に来る「悪意の無い馬鹿」を、止めたいんであれば、
そいつはその当時の熱気を知らないんだから、
「完全なコード」を乗せりゃいいんじゃね？
「そのコードに、自分が負けてるかどうかを簡単に検証できる」
用な環境を提示してやればいいんでは？

っていうか、428のコードは、何をどうするコードであって、
どうすれば「素数列挙」のコードになるの？

２年後にスレを観始めた人が、
そんな、細かいとこまでちゃんと、不完全な物も含めた全コードを、
main関数とかをちゃんとくっつけて、コンパイルして、検証すると思ってたの？
400MHzのプロセッサで50秒かかるコードを。

なんで、428のコードがあれば「悪意の無い馬鹿が日記を書き始める事は無い」
っておもったの？

>>940 にあるような、コードの訂正を、読んでる側の、「悪意の無い馬鹿」がやると思ってんの？
なんでさ、「完全なコード」を掲載しないの？

っていうか「428」のコードに、改造が必要だったのはなんで？

さらに、一億列挙するのに1.8秒のコードがあるのに
1億列挙するのに7秒かかるコードを「最低線」に選んだ理由はなに？

まあ、俺は939のコードに１億までの列挙で1200msecほど負けたので
もそっと精進しますが。

>>943
考え方はいろいろあるだろうけど、
やる気のある人間がやる気のない人間のスペースを奪うというのは
２ｃｈ的というより一般的な現象だね
君が向上しようとしていないから、どうすればいいかも分からないんだろうし、
泣いて哀れみ誘うしか止める手段がないんだろうね

1億1.8秒のコードはどうも怪しい気がするんですが俺だけですか。

>>947
単なるマシンパワーなんじゃないの？

unsigned char * PrintPrime( unsigned int nn ){
const n = nn - (nn % 6 == 0 || nn % 6 == 5 ? (nn + 1) % 6 : nn % 6 - 1);
const MAX3=n/3; unsigned char * tbl = malloc(MAX3/8); unsigned int m=1,n1,n2, x;
memset(tbl,0,MAX3/8);
while (m <= sqrt(MAX3/3)){
if(!TestBits(tbl, m) ){
x = m*(3*m+4)+1;
n2 = 6*m+4; n1 = 2*m+1;
PutsInt(3*m+2);
while( x<MAX3){SetBit(tbl, x); if(x+n1>=MAX3) break; SetBit(tbl, x+n1); x += n2;}
} m++;
if(!TestBits(tbl, m) ){
x = m*(3*m+2);
n2 = 6*m+2; n1 = 4*m+1;
PutsInt(3*m+1);
while( x<MAX3){SetBit(tbl,x); if(x+n1>=MAX3) break; SetBit(tbl,x+n1);x+=n2;}
} m++;
}
for(; m < MAX3; ){
if(!TestBits(tbl, m)){
PutsInt(3*m+2);
}m++;
if(m >= MAX3) break;
if(!TestBits(tbl, m)){
PutsInt(3*m+1);
}m++;
}
return tbl;
}

939はいろいろ間違ってたので上は修正版。
改行減らすために見にくくなってしまった。
>>946
過去のコードを読まないなんてすごいやる気だね。
俺やる気ないからそこまで適当に発言できないわ。
そんな漏れのコードはこれ
http://primes.dnip.net/primes.tar.gz
>>859 にある5番目のテクニックを使うともっと早く
なるんだけど、あんまり綺麗じゃないから実装前のやつ。

しつこく保守してるヤシがいるなあと思ってたのに...

なんもやらなかった人間にくらべりゃどんなやつだってやる気あるだろ。
「〜と思ってました」
「自分が望んだのはこんなんじゃありません」
「私は暗にこういうことを伝えたかったんです」
「好きにすればいいです」
なんもせずにそういう言葉を平気で吐ける人間と
実際にがんばる人間だったらがんばる人間を応援したくなるよ。

無駄ながんばりなんだよな･･･

風邪引いて仕事してて
「あー私風邪でも仕事がんばってるなー」
なんて寝言ほざいてる馬鹿と一緒じゃん
迷惑なんだよ
と何度いいそうになったことか
自分中心で考えてて
周りのことを考えることができないんだろうなと思った。

>>952
風邪で仕事来ないでください。伝染ります。

で、>>949 のコードを見てみたんだが、
「見つけた素数の倍数を、マークする(ふるう？)処理」って言うのは
√maxまででいいんだな。
そりゃそうか、
素数pをみつけたとき、pより小さい素数の倍数って言うのはすべてマークしてある。
つまり「pとp小さい素数の積」ってのはすべてマークしてある。
ってことはpの自乗よりも大きい数だけ、マークすればいい。
ってことは√maxよりも大きい素数を見つけた時は、
マークすべき数が無い、ってことか。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/47.txt

% time ./furui8 100000000 > prime_list8
5.780u 0.500s 0:06.68 94.0% 0+0k 0+10io 0pf+0w
1億で6.68秒。７秒切った。

time ./furui8 1000000000 > prime_list8_2
68.970u 5.870s 1:22.28 90.9% 0+0k 0+46io 0pf+0w
10億だと83秒。すげ速くなった。

あとは「素数pを見つけたときに、pの自乗より大きい数だけマークする」ようにすればもっと速くなる。
この回答の為のヒント( つーか答え )は、>>949のコードの
x=m*(3*m+4)+1 とか x=m*(3*m+2) にあるだろう。
これが漏れの中で飲み込めたら、実装しようと思う。

なにも調べないで他人のスペースを奪うやつが「やる気ある人」、「がんばる人間」。
煮詰まって発言が少なくなったやつは「やる気ない人」、「なんもやらなかった人間」。
やる気ないスレにやる気ある人が書き込んでんだから足引っぱるんじゃねえ。

過去ログ読めないやつのための859だった訳だがそういう問題じゃなかったと。

さて、>>950のコードでも読もうか...

漏れの環境で
% time ./primes -p 100000000 > prime_list
9824 + 65536 = 75360
3.840u 0.630s 0:04.81 92.9% 0+0k 0+1io 0pf+0w
1億まで4.8秒？...漏れが学ぶべきポイントは多そうだ

http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/77.txt

% time ./furui11 100000000 > prime_list11
4.980u 0.530s 0:05.87 93.8% 0+0k 0+12io 0pf+0w
1億で6秒切ったﾜｰｲ

% time ./furui11 1000000000 > prime_list11_2
60.270u 5.740s 1:08.57 96.2% 0+0k 0+49io 0pf+0w

planet risk見たいと思ったが。
radeon9000proで見れんかった。
グラボはみんな何で見てる？
demo起動->ゲフォ必要->電源落としてカード取り替え＆ドライバ再ｲﾝｽｺ->( ﾟДﾟ)ｳﾏｰ
このくらいの気合があれば良いんだろうけど・・・・

グラフィックカードに素数列挙させるの？だったら凄そう。

SSE使えないかな

awe

少しコードを削ってみた。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/183.cpp

% time ./furui13 100000000 > prime_list13
4.780u 0.600s 0:05.76 93.4% 0+0k 0+11io 0pf+0w

% time ./furui13 1000000000 > prime_list13_2
58.860u 5.530s 1:08.00 94.6% 0+0k 0+83io 0pf+0w

950並のループ展開が必要なんだろうか。
( すこしだけループ展開をしてみたりもしたんだが、むしろ遅くなったので、ループ展開に関しては、あんまり追求していない )
あるいは、２、３の倍数を除いた篩のとりあえずの極限に落ち着いてるんだろうか(ははっ、まさかね)。

2、3の倍数だけを抜いた方が、２、3、5を抜いた篩よりもコードが単純になる分最適化が効きやすかったりして有利かとも思ったが、
やはり859にあるように2,3,5を抜いた方が探索空間が小さい分だけ有利なんかなあ。
コードの単純さだと、950のは相当単純な反復に落としてあるし。

保守野鉄郎

CPU換装したら、ここで試せや↓
http://www5e.biglobe.ne.jp/~liquor/prime/

これ、動かないよ？アクセスバイオレーションとか

primeベンチか、VC++6で作られてるから、
古すぎて動かないやつもいるのかもね
作者が古いのか、OSが新しすぎるのかｗ

MAC用もｷﾎﾞﾝ

新たな参戦を求む

さいしょから2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97の倍数を抜いちゃったら？

>>969
やってみれ

　　　　　　　　　　　　　　　　　　　　,　-=-　-─‐-､
　　　　　　　　　　　　　　　　　　 _ ´-─　¬く ￣ ￣ﾐ- ､
　　　　　　　　　　　　　　　　,,,,／　　　　_==-ﾐｧ-─‐-､　＼''''''''''''ｰ--､,,,,,_
　　　　　　　　　　　　_,,,,-''"／　　,　‐''"　　　　　　　　　＼ ＼､_,,,ｰ''ゞ" `ゞ､
　　　　 　　　　 　 -' "　　/　　／　　　　　／　　　|　 　 　 ＼ ヽ 　　　　/"`
　　　　　　　_,,-''''''"""''''' /　／　 ／　　 / /　　　 ||　 |　　i　 ヽ i　　　 /
　　　　　　　´"''､.　　　　i　/　　/　/　　/ / /　 　 ||　 ||　　|│ |ﾉｽ 　/
　　　　　　　　　　'､　　 |//　 /　/___, -一ｧ|　　/! |ﾄ、|│　|　|　く」／
　　　　　　　 　 　　'､　 |,-‐¬　　---┘'７ |!　 ﾊ! |,､-┼十|!／＼／＼
　　　　　　　　　 , -‐ ''"　　し' '´_ ／,ィ二l |ﾄ、/!ヽﾄ､＼_ヽ!|!l＼:..　　／
　　　　　　　,r／　　　　　　__　　 ,イ|ﾘ ヾハ! ヽ!　 ,ィ⌒ヾﾐﾘﾉ／:::...　＼
　　　　　 ／ ||ヽ　　-'　　 　 ／￣ )｀　__　　　　　　|ヒﾉ:} '` ,;＼／＼／
　　　 ,r '　　 ヾ､　　,-､＿___ , イ￣,r=＝-　　　　　　==-'　 ﾚ' /|　 |
　　／　ヽ　　　 `ーｿ　 '　|　|ﾄ､,ﾍ ′""　　　　　　　 　 "" / / ||　|
. ／　　　 ＼_　　／　　|　ﾊ　ヽ｀ﾞ'ﾍ　　　　　　 ' '　 　　　／ / | |　 |　　　　　　　1000GET
　　 　 　 　 　 ／　　 /　/ |　 ヽ 川＼　 　 　　0 　 　 ／/! |　 | |　 |
　　　　　　　 /　　　 /　/ 八　 ＼川| |`ト-　..　__ ,　イ‐ｧﾍ |　 | ||　 |!
　　　　　　／　　　 /　/ /　 ＼　 ＼ 「`ー- ､　　　　／ 　.〉　 ト､|　 ヽ、
　　　　 ,イ　　　 ／-─＝¬ﾆヘ､_　 ＼ 　 厂＼　厂ヽ　/!| 　 |　`ｰ＝ﾍ
　-‐ ￣ /─　' ￣　　　　　├-　ヽ＼　 ＼ﾉ＼　＼　人 ﾊ!ヽ　||　　|-┤ ヽ
　 　 　 /　　　　　　　　　 ／!‐--　| |＼ 　 ﾄ､_｀ヽ oヽ　　ﾄ､!　 ||　　|‐┤- ヽ
　　／/ 〉　　　　　　__ ／　 ├‐-　 ||　 | 川-‐　　|　|　　厂7! ﾊ!　 ├:┤　￣ヽ
　　／ / ｰ ─ 　 ￣ 　 　 　 ├‐-　ﾘ　 || ﾊ!ﾍ　　 |　|　　ト┤|/′　ヾ,┤　　　ﾞi_
　　‐ '　　　　　　　　　　　　　 〉‐-　　　 | /　/＼ .|o |　/ヽ/（′　 　 ∨　　　　 ＼

２，３だと６のうち２つ
２．３．５だと３０のうち８つ
２，３，５，７だと２１０のうち４８

ΠpのうちのΠp-1

974get

２種類の分銅A,Bを使って、じゃがいも1gの物を量るために
成分A,Bを求める、またその正当性も求めるというアルゴリズムは
どのようにかけばいいのでしょうか？
知ってる方いましたらどうかおしえてください。

>>975 マルチ士ね

>>976
知らないならほっといてください。
知ってる方いましたら
どうかおしえてください。

拡張ユークリッドの互除法

拡張ユークリッドの互除法
は最大公約数を求めるものですよね？
それをどういうふうにつかえばよろしいのでしょうか？

自分勝手なやつだな。
ほっといたら迷惑なんだよ、お前は。
ここにいちゃいけない人間なんだってことを理解しろ。

>>980それは君
いくつものスレに迷惑文ばっか載せて
他人迷惑をかけている。

利用規約に反しているので
運営側に報告
IPアドレスから所在地をつかみ
損害賠償

ｵﾒ

ﾃﾗｷﾓｽ

>>934
むしろ神父さん。

>>982
あ〜
怖くなったのか。
乙

ｶｺｲｲ！ﾄｵﾓﾃﾙﾉｶﾅｼﾞﾌﾞﾝﾃﾞﾜ

>>986あなたは利用規約に反しています。
再三の忠告にも関わらず
迷惑行為をしていますので
利用規約違反者として
あなたの通信記録より身元を判明させて頂き、
警察等に連絡させていただきます。