素数 "列挙" アルゴリズムを極めるスレ
レス数が1000を超えています。これ以上書き込みはできません。
00011
NGNG既存のソフトも参考に挙げるべきか？
0002デフォルトの名無しさん
NGNG0003デフォルトの名無しさん
NGNG挙げるべきかじゃねーよ
スレ立てるなら参考ページからソフト、
関連技術などのリンクそろえておけ
0004デフォルトの名無しさん
NGNG0005デフォルトの名無しさん
NGNG既存スレ
最速の素数判定アルゴリズム
http://pc.2ch.net/test/read.cgi/tech/993457354/
まだ使えるから そっちでやってよ
00061
NGNGどっちでもないです。
>>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
00071
NGNG判定と列挙は微妙に違います。向こうで書くと微妙にスレ違いになりそうだったので。
0008デフォルトの名無しさん
NGNG0009デフォルトの名無しさん
NGNGそこのリンク、ものすごく低レベルなんだが、
もしかして10桁とか20桁とかそういうものすごい低レベルな話？
数百万桁クラスの素数って事じゃないのか？
メモリ使用量も考慮してとかあるし。
リンクを見る限り、１自体がこの話題についてこれる気配がしないんだが
00101
NGNGそのとおりです。凄く低レベルです。
数百万桁クラスの素数を列挙する方法があるんですか？
0011デフォルトの名無しさん
NGNG作ったこともない奴が作った奴を批判する資格はない。
0012デフォルトの名無しさん
NGNG列挙できるのは64bitでも限界に近いよ
0014デフォルトの名無しさん
NGNGどうせなら100桁（40バイト）くらいの素数を与えてそこから素数を列挙するとか
0015デフォルトの名無しさん
NGNG64bit限界はエラトステネスのふるいを使った場合
00161
NGNG100桁の素数辞書のサイズが莫迦にならないと思うんですが…
0017デフォルトの名無しさん
NGNG0018デフォルトの名無しさん
NGNGまさか確率判定法でフルイを粗くさばく？
0019デフォルトの名無しさん
NGNG0020デフォルトの名無しさん
NGNG0021デフォルトの名無しさん
NGNG0022デフォルトの名無しさん
NGNG0023デフォルトの名無しさん
NGNGn0 := 170141183460469231731687303715884105727
n0 ～ n0+0xffff の範囲の素数を列挙せよ
0024デフォルトの名無しさん
NGNG2^127-1 = 170141183460469231731687303715884105727
0025デフォルトの名無しさん
NGNG0026デフォルトの名無しさん
NGNGてめえらここにソース出してみろ
0027デフォルトの名無しさん
NGNG0028デフォルトの名無しさん
NGNGｵﾏｴﾓﾅｰって言ってほしい？
0029デフォルトの名無しさん
NGNG0030デフォルトの名無しさん
NGNG0031デフォルトの名無しさん
NGNGそれが可能なら現在のネットワーク社会が
おそらく崩壊するのだが…
0032デフォルトの名無しさん
NGNGなどと間口を広げてみるテスト。
0033房
NGNG0034房
NGNG電子フロンティア財団(EFF)が、今までで最も大きな素数の発見に対して、最大25万ドルを提供しようとしている。
問題は、誰も1人では賞金をもらうことはできないだろうということだ。
この賞金を得られるほど大きな素数を発見するには、世界最速のスーパーコンピューターでも6万2000年かかると考えられている。
こんなことがあったYO
2chのみんなで25万㌦山分けｼﾏｯｼｮｲ!
0035デフォルトの名無しさん
NGNG最速の素数判定アルゴリズム
http://pc.2ch.net/test/read.cgi/tech/993457354/
ここはちょっと違うよー
0036デフォルトの名無しさん
NGNGプログラムの練習で書くような場合。
0037デフォルトの名無しさん
NGNGいいんじゃない？ てか俺それ以外に思いつかない。
0038デフォルトの名無しさん
NGNG0039デフォルトの名無しさん
NGNGもちっと詳しく説明きぼんぬ。
0040デフォルトの名無しさん
NGNGextern "C"{
int printf(const char*,...);
long atoi(const char*);
}
main(int c,char *v[]){
unsigned long m,q,r;
if(1<c){
m=atoi(v[1]);
char*P=new char[m];
for(q=3;q*q<m;q+=2){
if(P[q]!=1){
for(r=q*q;r<m;r+=q+q)
P[r]=1;
}
}
printf("2\n");
for(q=3;q<m;q+=2){
if(P[q]!=1)
printf("%u\n",q);
}
}
return 0;
}
これどうよ？
もっと短くできっか？
0041デフォルトの名無しさん
NGNG0042デフォルトの名無しさん
NGNG> もっと短くできっか？
速度を気にしないならこんなのが７行スレにあったが。
#include <iostream.h>
int main(){for(int z,i=1;z=++i;){while(i%--z);if(z==1)cout<<i<<",";}return 0;}
0043デフォルトの名無しさん
NGNGそれ最短極めたと思う。クソ遅いけどｗ
てわけで最短はこれでｹﾃｰｲ?
0044昔それ>>42書いた人
NGNGつーかスレ違い。
>>36,38
２から順に全部探してく方法だと、それが最速じゃないかな。
もっと条件を課してくと別のアルゴリズムがあるかもしれない。
俺はよく知らんけど…。
0045デフォルトの名無しさん
NGNG0046デフォルトの名無しさん
NGNGに63bit以下の素数全部載ってるよ
0047デフォルトの名無しさん
NGNG検索中のページは、削除された、名前が変更された、または現在利用できない可能性があります。
0048デフォルトの名無しさん
NGNG0049デフォルトの名無しさん
NGNG0050デフォルトの名無しさん
NGNGつまんね
0051クレジャパン
NGNG0052ヽ(´ー｀)ノ
NGNG0054デフォルトの名無しさん
NGNG速くするんだったらforループをq+=10とかにして
1の位が1、3、7、9のものだけ調べるとかじゃだめ？
難しいことわかんないけど。
0055デフォルトの名無しさん
NGNGちょっとやってみよう
0056デフォルトの名無しさん
NGNGやってみようと言ったものの実行する前にふと気づく。
if(P[q]!=1){
で判定するから速さはあんまり変わらない気がする。
0057デフォルトの名無しさん
NGNGそれから、そのコードでは32bitフルに素数を列挙出来ない。
列挙するにはビットマップでフラグを持ち
さらに 2と3の倍数を最初から除くようにする。
http://pc.2ch.net/test/read.cgi/tech/993457354/128
0058デフォルトの名無しさん
NGNGあっそうか！
自分が前に作ったのは小さい素数から順にファイルに保存してくやつだったから。。。
エラトステネス使ってたら意味ないか。。。
0060デフォルトの名無しさん
NGNG最速の素数判定アルゴリズム
http://pc.2ch.net/test/read.cgi/tech/993457354/
のスレで既に話が出てると思うが、素数を保存する方法としても
整数として値保存するより、フルイをビットマップで保存する方が効率が良い
0061デフォルトの名無しさん
NGNGC初心者なのでソースが読めません…
0063デフォルトの名無しさん
NGNG実は>>40書いたの俺なんです…
0064デフォルトの名無しさん
NGNG除く処理がちと面倒…かな？
0065デフォルトの名無しさん
NGNG6の倍数に1足したら素数確定ですか？
0066デフォルトの名無しさん
NGNG25=6*4+1
0067デフォルトの名無しさん
NGNG0068デフォルトの名無しさん
NGNGttp://f1.aaacafe.ne.jp/~pointc/log59.html
セコイのでsage
0069デフォルトの名無しさん
NGNGそのテーブルを作るプログラムを考えねば話にならんな。
ネタ募集あげ
0070デフォルトの名無しさん
NGNGprimes = sieve [2.. ] where
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]
だな。
0071デフォルトの名無しさん
NGNG「なんでもあり」なのに is_prime 使ってるのはなんでだろう？
while(n=next_prime()){
～
}
------
unsigned long next_prime()
{
static const unsigned long *ptr = prime_table;
return *ptr++;
}
でよくね？
0072デフォルトの名無しさん
NGNG小さい数字まで求めたいとき、プログラムのロード時間の方が大きくなって…
0073Delフサギコ ◆zE1iiRdQ
NGNG∧,,∧ ∬ ／フォルダわけて分割したﾃｷｽﾄファイルを
ミ,,ﾟДﾟノ,っ━~ ＜ 読み込んだ方がいいよ。
＿と~,,, ~,,,ﾉ＿. ∀ ＼＿＿＿＿＿＿＿＿＿
.ﾐ,,,/~), .| ┷┳━
￣￣￣ .し'J￣￣|... ┃ どこまでか知らんが
￣￣￣￣￣￣￣ .┻ 素数列を32bitIntegerMaxまで持ったら256MBとか512MB
程度のメモリが必要だったんじゃなかったかな。
0074デフォルトの名無しさん
NGNGということは、１００Ｍオーバーのアプリになるのか ｲﾔﾝ
0075デフォルトの名無しさん
NGNG2^32/ln(2^32) *4 -> 780MByte程
2^31/ln(2^31) *4 -> 400MByte
0076デフォルトの名無しさん
NGNG2と3以外の素数はすべて6n±1に現れる。
0077デフォルトの名無しさん
NGNGここでも素数バトルやってるみたい
ttp://haya.s5.xrea.com/cgi-bin/petit/petit.cgi
0078デフォルトの名無しさん
NGNGうん。
2以外の素数はすべて2n＋1に現れる。
2と3以外の素数はすべて6n±1に現れる。
そして2と3と5以外の素数はすべて30n±1, 30n±7, 30n±11, 30n±13,
30n±17, 30n±19, 30n±23に現れる。
だから？
0079デフォルトの名無しさん
NGNG何を勝ち誇ったように…
0080デフォルトの名無しさん
NGNG0081デフォルトの名無しさん
NGNG0082デフォルトの名無しさん
NGNG170141183460469231731687303715884105757 = n0 + 30
170141183460469231731687303715884105773 = n0 + 46
170141183460469231731687303715884105793 = n0 + 66
170141183460469231731687303715884105829 = n0 + 102
170141183460469231731687303715884105851 = n0 + 124
170141183460469231731687303715884105979 = n0 + 252
170141183460469231731687303715884106001 = n0 + 274
あといくつぐらいだろ。この割だと、1500こ前後だと思うけど。。。
0083デフォルトの名無しさん
NGNG170141183460469231731687303715884105727 = n0 + 0
忘れてた。
0084デフォルトの名無しさん
NGNG0085デフォルトの名無しさん
NGNGそれ、試行的除算法ですか？
0086デフォルトの名無しさん
NGNGそれだと 41 43 47 53 が重なる。
60n-30±x にして x=29 を追加。
0087デフォルトの名無しさん
NGNGそれでどこが「いいトコついてる」のか教えてくれ。
0088デフォルトの名無しさん
NGNG0089デフォルトの名無しさん
NGNGMiller 法です。
ですから Riemann 仮説が証明されないとこの結果も 100% 正しいとは
いえないのですが、現在のところほぼ間違いないといわれています。
私も証明はできないのですが、原理は簡単ですので、
興味がある方がいれば、原理だけなら、説明します。
さて、この範囲の探索に
pentium!!! 1.26GHz のマシンで4時間ほどかかりました。
結局、全部で 760 個の素数が見付かっています。
最後のは
170141183460469231731687303715884171179 = n0 + 65452
です。
Millwe 法で調べたので、これより多いことは
(私のプログラムミスが無いとすれば)ありません。
逆は Riemann 仮説が証明されるかにかかっています。
0090デフォルトの名無しさん
NGNG0091デフォルトの名無しさん
NGNGRiemann予想(Riemann Hypothesis)のこと？
0092デフォルトの名無しさん
NGNGMiller 法も、多分正確には "Miller-Rabin's Primality Test"
だとおもいます。以下、私の浅い理解レベルで解説してみます。
間違っていたら御指摘ください。
基本的にはフェルマーテストと、sqrt(1) が 1 or -1 である
ことをある範囲の数について確かめるのですが、この範囲が
Riemann Hypothesis が証明さればかなり狭い範囲でよいと言
うことです。
1. フェルマーテスト
フェルマーの小定理は、「p が素数なら、 0 以外のどんな a
についても、a^p \equiv a \pmod p」。(aをp乗してpで割った余り
がaになるってこと。この証明は簡単ですよね。)
さて、この命題の対偶は、(以下、TeXっぽい記号はよみにくいので
プログラム言語っぽく書きます。)
「ある a (!=0) について a^p%p が a でないならば、p は
素数ではない」。
です。そこで、ある数 p についてさまざまな a を持って来て
a^p%p を計算し、一つでも a にならない a があったらその時点で
p が素数ではないことが分かります。
ここで、注意ですが、1 <= a <=p-1 の全ての a について、
a^p%a=a になるのに、p が素数ではない場合があるってことです。
さらに捕捉ですが、a^p%p の計算は a, a^2%p, a^4%p, ... を作り
必要なのを掛け合わせます(%p しながら)。特に a や p が大きい
場合はそうしないと手間が極端に増加します。
0093デフォルトの名無しさん
NGNG0094デフォルトの名無しさん
NGNGや、実はその分野を勉強した人にとっては初歩の初歩なんよ。
専門分野が違う人に「おれって頭良いでしょ」とかますハッタリとしては
効果的なんだけどさ。
0095デフォルトの名無しさん
NGNG数学科だけかもしれないけど
0096デフォルトの名無しさん
NGNGそうなのか…ちょいと鬱だ
漏れはｴﾗﾄｽﾃﾈｽを2飛ばしでやるのが精一杯だYO...
0097デフォルトの名無しさん
NGNG0098デフォルトの名無しさん
NGNG0099Lisp 1.5
NGNGHaskellで書いた素数の無限リストのプログラム。
sieve (p : r) = p : sieve [ n | n <- r; n mod p ~= 0 ]
primes = sieve [2..]
:はconsの生成と分解。引数はパターンマッチング渡しで遅延評価。
一行目は、ZF記法っていう置換公理風のリスト生成。
二行目の[x..]は、[x, x+1, x+2, ...]というリスト生成。
0100デフォルトの名無しさん
NGNG速さはいかほどでしょう？
0101Lisp 1.5
NGNGmodの回数に関するO(n)は普通のエラトステネスの篩と同じです。
-- なこと、いわんでも分かってるか。(しかし何で素数判定法の話に…)
0102デフォルトの名無しさん
NGNG2番目の素数を求めよ （答え 3）
22番目の素数を求めよ （答え 79）
222番目の素数を求めよ （答え 1399）
という具合に 2…2番目の素数を求めよ。
N番目の素数を求めるには、それ以下の素数を全て列挙する以外方法はないだろう。
まぁ、10の整数乗番目の素数はweb 上にけっこう落ちているから、
それを利用すれば多少は処理を速くできる。
0103デフォルトの名無しさん
NGNG2222番目=19583
22222番目=252233
222222番目=3080969
とりあえず、ここまで求めた
0104デフォルトの名無しさん
NGNG確か２変数の多項式で、整数の値を入れた時、値が正になる限り素数
だったような...
全部求められなくとも、巨大な素数をいち早く見つける方法としては
有効かも.
0105デフォルトの名無しさん
NGNGprime generate polynomial で検索してみた。
見つかったのは、ものすごい26変数の多項式だけですた。
http://mathworld.wolfram.com/PrimeDiophantineEquations.html
こんな連立方程式とても解けねーっす。
0106デフォルトの名無しさん
NGNG0107デフォルトの名無しさん
NGNG今日もネタもないのにageてやるからな！
￣￣∨￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
∧＿∧ ∧＿∧ age
（・∀・∩）（∩・∀・） age
（つ 丿 （ ⊂） age
（ ヽノ ヽ/ ） age
し（＿） （＿）Ｊ
0108デフォルトの名無しさん
NGNGhttp://pc.2ch.net/test/read.cgi/tech/993457354/
このスレ落ちちゃったか・・・・
0109デフォルトの名無しさん
NGNG0110デフォルトの名無しさん
NGNGttp://www.klic.org/software/klic/lang/node134.html#SECTION008100000000000000000
0112デフォルトの名無しさん
NGNGがんがってくれ。健闘を祈る。
「素数でないものを初めから入力列から省き、効率的にエラトステネスを行う」
ということを実現したのだが……。
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%
つまり、本当の勝負である億以上の世界では意味が無くなってきているわけで……。
STL Listを使ったオーバーヘッドで、多分普通のエラトステネスに負けるでしょう。
ちなみに上記の時間はメモリ内にListで素数列を展開した時の時間です。
Pen4 1.6GHz / DDR-SDRAM 512 MBytes / Windows 2000 です。
0115デフォルトの名無しさん
NGNGここ参考になるかな？
0116デフォルトの名無しさん
NGNGhttp://www.kurims.kyoto-u.ac.jp/~ooura/pc_bench/prime.c
0117デフォルトの名無しさん
NGNGエラトステネスだろう。ビット演算多用してるので早そうだ
ただ make_prime_tab 中の k <= nh / 3 がよくわからん。
0118デフォルトの名無しさん
NGNG２と３の倍数をはじいてるからか？
0119デフォルトの名無しさん
NGNG0120デフォルトの名無しさん
NGNG0121デフォルトの名無しさん
NGNG0122多項式時間
NGNG0123デフォルトの名無しさん
NGNG0124デフォルトの名無しさん
NGNGsqrt()や乗算を使いたくなかったのだろう。
ビットを多用しているのはメモリ節約の為(1/32か)。
普通にエラトステネスの篩を使った場合と比べて速くなるかは微妙だな。
訳ではない、とここにも書いておきます。
（私自身は前回のがそれほど効率的でなかったことに気づき
やる気喪失ですが。やるなら2,3の倍数を飛ばすエラトステネスを
お勧めします)
現状まとめ（違ってたら訂正よろしくお願いします）：
判定と列挙は別、それに確率的判定なら今まででも出来たし、
現段階ではまだ決定的判定は多項式時間といえど遅すぎる。
0126デフォルトの名無しさん
NGNGところで◆.RANK1Kg氏、下のコードはどうでしょうか？
http://idm.s9.xrea.com/factorization/impl/eratosthenes/esieve4.c
0127デフォルトの名無しさん
NGNG速いですねー。しかもファイル出力まで作っちゃうし。
関連記事も読み応えあります。
挑戦する人は必読かもしれません。
私のは「根本的にオーダが改善する」期待があったので、
実際の時間よりオーダを気にしていた……と言い訳させてください。
（ちょっと考えればそんなことは無いことは分かったのですが、
私の数学力だと実際に作って確かめなければ分からなかった）
素数表を必要としないのが特徴ですが、
素数列挙の場合は自然数Nが素数か調べるときにN未満までの素数表が使えます。
これって生かせるんでしょうかね……。それが良くわからない。
生かせないとしたら、このスレの存在価値は無しなんですが。
生かせるとしたら、エラトステネスを超えるアルゴリズムはあるんでしょうか。
0130デフォルトの名無しさん
NGNGURL見るだけでエラトステネスだってわかるけど
1度作ってみると分かりますよ。
素数表を保持する性質上、メモリの無駄を抑えるところで差がつくんです。
0132デフォルトの名無しさん
NGNGextern "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;
}
0133デフォルトの名無しさん
NGNG0134デフォルトの名無しさん
NGNGほんとオマエらヴァカばっかだな。
オレが最速のソース伝授してやるよ。
今回は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]);
}
}
0135逝って良しの１
NGNG0136デフォルトの名無しさん
NGNG0137デフォルトの名無しさん
NGNGvoid 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より頭いい。
0138デフォルトの名無しさん
NGNG0139デフォルトの名無しさん
NGNGでも外出
0140デフォルトの名無しさん
NGNGM'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ちゃいます。
0141デフォルトの名無しさん
NGNG140です。
なんか、うまく展開できなさっぽいので、分割してみます。
全部くっつけてコンパイルしてみて下さいませ。
*/
#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;
}
};
0142デフォルトの名無しさん
NGNGclass 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();
}
};
0143デフォルトの名無しさん
NGNG// メインです。なくていい？
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;
}
0144逝って良しの１
NGNGhttp://gt.sakura.ne.jp/~nyagy/integer/sosuu_seisei.html
0145デフォルトの名無しさん
NGNGﾜﾛﾀ。
0146デフォルトの名無しさん
NGNGやったぜ、素数見つけた
0147デフォルトの名無しさん
NGNG60000個列挙に12分。
これってどう？全然戦えてない？
0148デフォルトの名無しさん
NGNGVectorあたりで何個か落としてみろ
0149デフォルトの名無しさん
NGNG10000個目、60000個目の素数が何だか知らんが
1000000までの素数を列挙する（ちなみに素数の数は78498個）のに
400MHzのCPUで0.75秒。
0150デフォルトの名無しさん
NGNGhttp://www.vector.co.jp/soft/win95/edu/se221945.html
0151デフォルトの名無しさん
NGNG# >>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
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
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
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に移植してみたのれす。。
# でも・・・・・遅いっすね★
0156デフォルトの名無しさん
NGNG俺はRubyのコトはよく分からんのだが過去レスに色々ソースがあるから
見てみ（大概Cだけど）。
がんがれやヽ( ´ー｀)丿
漏れの活躍してた素数スレが消えちゃったよ～★
1 ：移転したよ。。。 ：移転
移転しました。。。
こちらです。http://pc3.2ch.net/pc3tr/
↑ここ逝っても何もないしさぁ・・・。
0158デフォルトの名無しさん
NGNGしばらくすると消えるから必要なレスをコピペして。
http://pc3.2ch.net/test/read.cgi/pc3tr/1030500162/
0159デフォルトの名無しさん
NGNG頑張って勉強していたスレ、というなら認めるが。
活躍というなら、>>126を超えてくれ。
これ↓れした。いかな厨房でも理解できそうれす。
#!/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よりは早いのれす。
求めた素数をすべて配列に保持するアルゴリズムを
実装すると、かえって速度が落ちるようなのれす。
うひひ。
0162デフォルトの名無しさん
NGNG無駄レスするな。暗躍の意味をわかっているのか小一時間。
>>152より上を見るのがかったるくなってしまったが>>150は速いな…
がんがっていたのれすが、ポインタに対して
ビット演算してたりして、お手上げれした。
これから>>126を移植すべく、アサヒ スーパー
ドライを含んだ頭でせいぜいがんがります。
よろしく☆
0164デフォルトの名無しさん
NGNGかすみ遊戯のかすみみたいな口調虫唾が走る。
うひひ★どうせ漏れはﾄﾞｷｭｿれすよ★
ﾄﾞｷｭｿはﾄﾞｷｭｿらしくしてるのが
一番なのれすよ★
ﾊｧｧ･･･
0166デフォルトの名無しさん
NGNGお前が酒を飲むなんぞ10年早いわ。
だいたい >>126 のruby版は既にあるし。
20歳だから飲んでもいいんだもん★
つーか「かすみ遊戯」って何？
って思ってぐぐるしたら、エロゲじゃん。
げろげろげろー
＞だいたい >>126 のruby版は既にあるし。
なんてこったい★漏れとしたことが★
で、計ってみました★
（ただしこれまで同様printはコメントアウト）
$ time ./esieve4.rb 100000
Prime numbers such that p<=100000 are,
real 0m0.149s
user 0m0.140s
sys 0m0.015s
・・・・・・試合放棄してもいいれすか？
0168デフォルトの名無しさん
NGNGそうか、ここまでよく頑張ったな。いいよ。
いぢめっこがいるよ～★
┌─┐
｜も.｜
｜う |
│来│
│ね│
│え .|
│よ .|
ﾊﾞｶ ｺﾞﾙｧ │ !!.│
└─┤ ﾌﾟﾝﾌﾟﾝ
ヽ(`Д´)ﾉ ヽ(`Д´)ﾉ (`Д´)ﾉ （ `Д）
|￣￣￣|─|￣￣￣|─|￣￣￣|─□（ ヽ┐U
～ ～ ￣◎￣ .￣◎￣ ￣◎￣ ◎－>┘◎
0171デフォルトの名無しさん
NGNG0172デフォルトの名無しさん
NGNG0173デフォルトの名無しさん
NGNGていうか、sageてない？
0174デフォルトの名無しさん
NGNGsageのまま保守することがいけないことか？
0175デフォルトの名無しさん
NGNG禿同！！
保守はsageでするべきだと思う。
0176デフォルトの名無しさん
NGNGそういいながらageて書く君が好きだ
ちょっとでも速いアルゴリズムを書きたいが小手先の技になりそうだな…
0177デフォルトの名無しさん
NGNGやってみれば。
小手先の技でも塵も積もれば山となる…かも
0178デフォルトの名無しさん
NGNG0179DQN.cc
NGNG0180デフォルトの名無しさん
NGNGA>list 素数
1、2、3，5、7、11、13、17、19、23、26、29、31、37とでてくる。
A>
0181デフォルトの名無しさん
NGNG馬鹿31は素数じゃねぇよ
0182デフォルトの名無しさん
NGNG馬鹿はあんただよ…
0183デフォルトの名無しさん
NGNGと言ってみたかったと無理やり弁護してみるテスト。
0184デフォルトの名無しさん
NGNGは く さい
白菜
0185デフォルトの名無しさん
NGNG% 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」がバイナリ。
最初の引数が、ふるいの大きさ。
次の引数で、いくつめの素数を表示するかを指定( チェック用 )
アイデアがあるので、これから改造。
0186デフォルトの名無しさん
NGNGところで、999983 は78498番目の素数だと思う。
０からカウントをしているということか？
「いくつめ」という時は普通１からだよ
0187DQN.cc
NGNG改造したらソースきぼ～ん☆
0188デフォルトの名無しさん
NGNGttp://lecture.ecc.u-tokyo.ac.jp/~kuno/cp01/report/report2b.html
0189デフォルトの名無しさん
NGNG数はあるけど…
0190188
NGNG0191185
NGNG% 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行にもなっちゃった。
0192デフォルトの名無しさん
NGNG0193デフォルトの名無しさん
NGNG0194デフォルトの名無しさん
NGNG凄く厨な事聞いてるみたいで恥ずかしいのだが、
＞1.940u 0.400s 0:02.55 91.7% 0+0k 0+0io 0pf+0w ( G4 450MHz )
これの読み方がわからぬ(；´Д`)
何が何を表してるのか教えてくだされ。。
0196デフォルトの名無しさん
NGNGπ(x)～x/log(x)なんだそうな。
だからちょっとずつ頻度は低くなる。
0197デフォルトの名無しさん
NGNGファイルが見つかりません…
0199185
NGNGそれです！指摘サンクス！
なんで間違っちゃったんだろう....遅刻までして....
あー。死にたいなぁ。
ちなみに、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っぽいので、
この部分が短くなるように努力してます。
0200デフォルトの名無しさん
NGNG>>185さん 俺 C++知らないんだけど、
このプログラム class いっぱい使ってるよね。
これくらいのプログラムなら main にダラダラ書いてもいいんじゃない？
可読性は下がるけど、速度面では有利だと思う
0202デフォルトの名無しさん
NGNG0203デフォルトの名無しさん
NGNG0204デフォルトの名無しさん
NGNG七行スレに依頼しる！
0205デフォルトの名無しさん
NGNG見づらさが500％増加の見込み
0206ソースを読まずにカキコ
NGNGコンパイラによってはinline指定子もあるし。
まだレジスタの出入りの心配をした方がましかと・・・・・・。
0207デフォルトの名無しさん
NGNG0208デフォルトの名無しさん
NGNG0209デフォルトの名無しさん
NGNG30行？カスだな。
0210デフォルトの名無しさん
NGNG0211デフォルトの名無しさん
NGNGシンプルな問題ではあるが、奥が深い
素数自体がおもしろい数だし
0212デフォルトの名無しさん
NGNG賞金もらえるぞ
0213デフォルトの名無しさん
NGNG0214デフォルトの名無しさん
NGNG0215デフォルトの名無しさん
NGNG0216デフォルトの名無しさん
NGNG0217デフォルトの名無しさん
NGNG素数を全部入れなきゃ駄目？
0218デフォルトの名無しさん
NGNG0219デフォルトの名無しさん
NGNG速さを目指すなら、バイナリでファイルに出力することを推奨
0220デフォルトの名無しさん
NGNGバイナリだと何でもありになりそうだから…
0221デフォルトの名無しさん
NGNG出力0.0001秒、表示200時間とか？
0222デフォルトの名無しさん
NGNG0223デフォルトの名無しさん
NGNGそうだな。
じゃあテキストで、tab 又は 改行で区切るってことで。
個人的には , で区切るのはやってほしくない。
言語によっては、ファイルを読む処理がめんどくなる
0224デフォルトの名無しさん
NGNG全然プログラミングと関係無いねえじゃん。
数学板帰れよアホ。
0225デフォルトの名無しさん
NGNG禿しく慨出。
0226デフォルトの名無しさん
NGNG数学は列挙したりなどしない。定義さえすれば、そこにあるものだから。
そして利用する場合には、プログラム的なアクセスが必要になる。
0227デフォルトの名無しさん
NGNG0228デフォルトの名無しさん
NGNG0229デフォルトの名無しさん
NGNG0230デフォルトの名無しさん
NGNG1:エラトステネスの篩
2:順番に素数判定
の二つしか知らないのだけど、もっと素敵な列挙法ってないでしょうか？
0231デフォルトの名無しさん
NGNG素数データベースから読み出して表示
（列挙は列挙でしょ♪）
0232デフォルトの名無しさん
NGNG0233デフォルトの名無しさん
NGNG0234デフォルトの名無しさん
NGNG意味が良くわかんないんだけど。
説明していただけるかしら？
0235名無しさん ◆jZGaCDQNcc
NGNG21 は素数ですか?)(y/n) _n
21 は素数ではありません。
13 は素数ですか?(y/n) _y
13 は素数です。
（以下同じ）
0236デフォルトの名無しさん
NGNG0237デフォルトの名無しさん
NGNGプラス2の倍数を飛ばしてみたり。
上のほうに2と3の倍数を飛ばすのがあったけどそれ以上のはめんどくさそうだね…
0239デフォルトの名無しさん
NGNGあとは早い言語で、良い実装をする。これに尽きる
0240デフォルトの名無しさん
NGNG0241デフォルトの名無しさん
NGNGhttp://science.2ch.net/test/read.cgi/math/1033486518/
http://science.2ch.net/test/read.cgi/math/1030077269/
0242デフォルトの名無しさん
NGNG無限に存在する素数を相手にする時に限界があるよね。
2の倍数、3の倍数の枝刈りのようなもの。
0243デフォルトの名無しさん
NGNG俺たちにゃ有限の時間しか残されていないのだから、有限でいいのさ
0244デフォルトの名無しさん
NGNGa²+b²=c²な数を！
0245デフォルトの名無しさん
NGNG0246デフォルトの名無しさん
NGNG0247デフォルトの名無しさん
NGNGそれセンター試験でやった。懐かすぃ
0248デフォルトの名無しさん
NGNG敢えて isPrime系を選択してみた。
isPrimeには、平方根を求める操作が必須だ。
「sqrtのアルゴリズムは知らないが、
そんなに軽くないんじゃないの？」
そんな直感が、僕にこのコードを書かせた。
0250248
NGNG0251248
NGNG#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 という名前で。
0252248
NGNGPrimeEnumerator::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 。
0253248
NGNG#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 という名前で。
0254248
NGNG% 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 オプションをつけて、コンパイルした。
0255248
NGNG(int)sqrt( current ) に変更して実行してみると、
10000000までの素数の計算に、 3秒ほどよけいにかかるようになる。
30行ものコードを追加して、3/10000000 秒程度の
高速化しかなされていない。
今後 2や3の倍数をのぞいて計算できるようにもしようかと思ったが、
ばかばかしくなってしまった。
0256名無しさん ◆jZGaCDQNcc
NGNG$ 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になると数十秒待っても終わらなかった。
どっちばれ。
0257名無しさん ◆jZGaCDQNcc
NGNG#!/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
0258名無しさん ◆jZGaCDQNcc
NGNG>>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
0259名無しさん ◆jZGaCDQNcc
NGNGdef 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
0260名無しさん ◆jZGaCDQNcc
NGNGprotected
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
0261名無しさん ◆jZGaCDQNcc
NGNGi = (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
0263名無しさん ◆jZGaCDQNcc
NGNGWindows 2000 Pro SP3 + Cygwin 1.3.12 + ruby 1.6.7
AMD Athlon XP 2100+ (1.73GHz), RAM 512MB
UD, Winny, Mozilla, かちゅ～しゃ常駐 です。
0264デフォルトの名無しさん
NGNG0265名無しさん ◆jZGaCDQNcc
NGNGRubyが遅いだけ、と思いねぇ。
$ 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
0266デフォルトの名無しさん
NGNGもっとRubyらしくした方が、高速になりませんか？
0267デフォルトの名無しさん
NGNGちと高いが
0268デフォルトの名無しさん
NGNG#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;
}
0269デフォルトの名無しさん
NGNG0270デフォルトの名無しさん
NGNG30点。
正常に素数を列挙することに精いっぱいで
高速化のための工夫がまるでありませんね。
ただ、どんな本やお勉強サイトにも
こんなコードは載ってないでしょうから、
>>268さん自身が自力で書いたコードであることが解ります。
この点は、評価に値します。
今後は、以下の点に注意してがんばってみましょう。
「数が素数かどうかを調べるための % 演算の回数を
できるだけ少なくする。」
期待していますよ。
0271名無しさん ◆jZGaCDQNcc
NGNGn(1) = 2
n(2) = 3
n(3) = 5
n(4) = 7
こういうのを満たす関数って見つかってるの？
最高100までとかの制限はもちろんありだけど
最高どこらへんまで有効な式が見つかってるのかなあ。
0272デフォルトの名無しさん
NGNG引用してよぅ。すごい興味あります...
0273デフォルトの名無しさん
NGNG関数の形で素数を表現するだけでしたら、
集合 {y | gcd(1,y)=1, y!=1} に順序を与えればよいってことで。
0274デフォルトの名無しさん
NGNG0276デフォルトの名無しさん
NGNG「任意の有限の数列を表現する 一般的な方法」
をみた気がする。
0277デフォルトの名無しさん
NGNGﾊｧﾊｧ･･･ｴﾄﾗｽﾃﾈｽ!(・∀・)
0278ｴﾄﾗｽﾄﾃﾄﾗｽﾄｽﾃﾈｽ
NGNG0279デフォルトの名無しさん
NGNG不安になってググッちまったよ。
残念ながら、エトラステネスでは一件もヒットしなかった。
0280デフォルトの名無しさん
NGNGその関数はある･･･からこそ計算機で計算もできる。
有無じゃなくて、計算にかかる時間が問題になってるわけです。
0282デフォルトの名無しさん
NGNG>>275が欲しがっているのはシーケンシャルな計算なしで、
一発で( O(1)で )素数を求めるための式でしょ。
アルゴリズム的な方法をとるのなら、
int prime( int i ) {
static const int p[100] = { 2, 3, 5, 7, 11 , ... };
return p[i];
}
みたいな関数作っておけばいいだけなんだけども。
数学的な数式となると...数学板で聞いた方が早いかな。
0283267
NGNGhttp://www.nippyo.co.jp/maga_suutano/st28.htm
ｽﾏﾝ 立ち読みで済ませてしまった。１６００円もするから。
内容は、素数のいろいろな定義の仕方から始まって、
素数の数え上げ、素数の間隔、双子素数など。
ページ数もかなりさいてある。図書館にあればコピーしたいなぁ
0284名無しさん ◆jZGaCDQNcc
NGNGたとえば
(A) n + 1
ならnが1から2までなら成り立つっしょ？
こんな感じの簡単な数式が欲しいのれすが、
どうもスレ違いな予感。。。
0285デフォルトの名無しさん
NGNG確かものすごい次数の式になった気が。
つかそんなんあるんだったらとっくに出てると思う。
＃「そんなん」で「成男」出たよ。なんじゃこりゃ
0287デフォルトの名無しさん
NGNG100までの素数を解にもつ多項式なら作れるじゃん。
たとえば10までだったら
(x-2)(x-3)(x-5)(x-7)=0
これが>>286がほしい方程式じゃん。
0288デフォルトの名無しさん
NGNG0289287
NGNGf(x)=ax^3+bx^2+cx+d
と置いて、
f(1)=2,f(2)=3,f(3)=5,f(4)=7
を解けば未知数4個で式も4つだから10以下の素数求められるんじゃん？
同じように力技で100だろうが1000だろうがいけると思う。
素数がわかってなきゃ解けないから意味ないけど。
0290287
NGNG何度も書き込みすまそ。
0291268
NGNG超すごいよ
#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;
}
0292デフォルトの名無しさん
NGNG0293デフォルトの名無しさん
NGNGfprintf(stdout,"計算中です！！（止めないで）");
fprintf(stderr,"（次の素数をお願いします…（こそーり））");
scanf(&x);
fprintf("あ？次の素数？%dに決まってんだろボケ",x);
}
0294Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNGhttp://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1035246186
＿＿＿＿＿＿＿＿＿＿＿＿＿
∧,,∧ ／
ミ,,ﾟДﾟ彡 ＜ 書いてみたです。
,;ﾞ ﾐ ＼
＠ﾐ,,,UUﾐ ￣￣￣￣￣￣￣￣￣￣￣￣￣
ｴｽﾄﾗの2の倍数/3の倍数を使ってみますた。
そんなに高速化できませぬですた。
0295ｴﾄﾗｽﾄﾃﾄﾗｽﾄｽﾃﾈｽ
NGNGだから、ｴｽﾄﾗとかかかないでよ！
どれが正解だか解んなくなるしさ！
>>291
40点。
だからさ、countが2になったらループ続ける意味ねーだろ。
0296Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNGコメントないの？
0297デフォルトの名無しさん
NGNG１億 or １０億 or 2^31 or 2^32 以下の素数を求めるのにかかかる時間と実行環境ｵｾｰﾃ
0298ｴﾄﾗｽﾄﾃﾄﾗｽﾄｽﾃﾈｽ
NGNGすまん。つーか、コード長過ぎて、見る気がせん。
のんきな人だったら、週末まで待ってくれ。
あと、計算時間と実行環境は知りたいなぁ。
Delphi なんて持ってないし、ってゆか漏れマカーだし。
0299Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧ ／
ミ,,ﾟДﾟ彡 ＜ すごく遅いはずよ。
,;ﾞ ﾐ ＼
＠ﾐ,,,UUﾐ ￣￣￣￣￣￣￣￣￣￣￣￣￣
ﾋﾞｯﾄごとで素数か否かを判断して
2の倍数と3の倍数を削除してるだけだから。
ドノーマルのフルイです
メモリ使用量は少ないので.
容量が必要でオチるのはないと思うですが
あとはどうやって高速化するんですか？
･･･いや、激しく外出だとは思われなんですが・・・
0300Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG⊂,,,,,,,,,つ,,ﾟДﾟﾐつ
このｽﾚ、、住人少ないの？
0301デフォルトの名無しさん
NGNG0302Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG⊂,,,,,,,,,つ,,ﾟДﾟﾐつ Int32.Maxまでの素数は
求まっていなかった,,,もしかしたら300日くらいかかる？
0303デフォルトの名無しさん
NGNG0304デフォルトの名無しさん
NGNG＞どうせなら 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を足すようにすると、
コードは増えますが、その実行サイクルはメモリアクセスに完全に隠れてしまいます
0305デフォルトの名無しさん
NGNGTBitsを使うなら、最初にそのサイズを取得しておく方がいいです
また、この命令中に分岐が入っているので、遅い場合もあります。
偶数を無視して書き込む場合
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;
0306デフォルトの名無しさん
NGNG速度を考えるならホントはループ中に入れない方がいいです。
偶数でも値が2の時はTrueを返すとかの処理も
ただ、SetBitに比べると頻度はずっと小さいので
Test関数が遅くても それほど遅くはならないですが
0307Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧ ／
ミ,,ﾟДﾟ彡 ＜ さんくすこですー
ﾐ つ日 ＼＿＿＿＿＿＿＿＿＿＿＿
.＠ﾐ,,,,,, ,,ﾐ
>それをMove関数を使ってコピーし、
理論は理解しました。
でも。その初期化処理を具体的に
どう実装するのかがわからんですの。
TBitsとかTBooleanDynaArrayとかTListとかだと
ＩｔｅｍやBitsをＭｏｖｅで初期化するのって
どうやるのでしょうか。
そもそも、全てをＴｒｕｅにするのも、すごい初歩的な
やり方しかしてないので、その辺りのメモリ操作を
教えてください。>>304
> たとえば 17 19 をペアにして x,yの小さい方に xなら17 yなら19を足すようにすると、
> コードは増えますが、その実行サイクルはメモリアクセスに完全に隠れてしまいます
ごめんなさい。理解できません。偽コードで示していただければ
わかるかもなのですが...
と、書いてから305以降をﾊｹﾝしますた。読んでみます。
詳しい説明ありが㌧
0308デフォルトの名無しさん
NGNGvar 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
0309デフォルトの名無しさん
NGNG最初に似た値に近づけておいて 2*n*mの同じブロックサイズで検索するというものです
n,mが多くなると効果が出ませんが、n,mが大きくなればどうせ同じメモリバスを指す確率も減るので
n,m<200程度で使うと良いでしょう。
完全に隠れるという訳にはいかないけど、効果のある節約です
もっと多重にすればもっと効果が上がりそうですが、条件判断を増やさないでやるのは難しいです。
0310デフォルトの名無しさん
NGNG普通に書けば32bitのふるいはメモリが300Mあるマシンなら10分もかからないで完成する筈ですから
0311デフォルトの名無しさん
NGNGnの倍数を埋める場合、6で割った余りが 1と5の時だけ埋めれば良いので
n2:=2*n n4:=4*nと用意しておいて、交互に足します
７の倍数を埋める場合 初期値x=7*7=49 6で割った余りは１なので 49を埋めた後次は x:=x+n4 その次はx:=x+n2とループします
0312デフォルトの名無しさん
NGNG2,3の倍数を表から除いた場合、
セットすべきビット位置は x div 3 で 求まります。
0313デフォルトの名無しさん
NGNGn:=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にしておいた方がいいです
0314Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNGfunction TPrimeListTBitsTripleOverCompress.AccessInsideIndex(
OutSideIndex: Integer): Integer;
begin
Result := ((OutSideIndex div 6)*2)
+
((OutSideIndex mod 6) div 5);
end;
こんな感じだと思ってたのですが、
これって、x div 3 なのでしょうか？
|,,∧ ･ ・ ・ ・
|Дﾟ彡
| U
| ﾐ
| U
0315デフォルトの名無しさん
NGNG最初に5 2を足して7 4を足して 11 2を足して13 というふうに回るからです。
そこで n=6*k+1 と n=6*k+5 と書きます
すると、n div 3 は 2*k か 2*k+1になりますね？
0316Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG|,,∧ ｱﾗﾔﾀﾞ すごいわぁ
|Дﾟ彡
| U
| ﾐ
0317デフォルトの名無しさん
NGNG除算は整数でも浮動小数点ユニットが使われたりで、並列演算が出来ないから
そういうふうに連続して使わない方がいいよ。 合計３つも連続して使うとストールする。
0318Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG|Дﾟ彡 ファイルにして、1ｷﾞｶﾞになちゃう勢いなんですが
|⊂ﾐ …
| ﾐ Webにウプする場所がない…
|''U そもそも、俺の56K回線では…
0319デフォルトの名無しさん
NGNG0320デフォルトの名無しさん
NGNGフルイの状態が一番効率がいいんだよ。だからフルイのままで持っておいて問合せに対して
出力させたら？ でも100MもRAM取ると鯖屋に嫌われるか
0321デフォルトの名無しさん
NGNG0～N を１０進で改行付で列挙する場合のおよその必要バイト数
N*(log10(N)+2)/loge(N)
l
0322デフォルトの名無しさん
NGNGどのコードを？
0323デフォルトの名無しさん
NGNG>>305,308,313
つまり全部…
0324デフォルトの名無しさん
NGNG{ 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;
}
0325デフォルトの名無しさん
NGNG{ 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);
}
}
0326デフォルトの名無しさん
NGNGint 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;
}
0327デフォルトの名無しさん
NGNGint 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
0328デフォルトの名無しさん
NGNGどこから来たの？どのような概念？
>>324～
どのようなことを考慮したプログラムなの？
ゴメン、詳細キボン
0329デフォルトの名無しさん
NGNGただし TBitsは無いので SetBits/TestBitsの関数に置き換えました。
それと、0～0xFFFFFFFF の範囲の列挙ができるようにしています。
マシンに256M以下のメモリしか無い人は実行すると異常に遅くなるでしょう。
>>304 の件は >>310 の通り、実施してもビックリする程早くはなりません。
>>324 のようなテクニックの方が確実に早くなると思います
0330328
NGNG感謝します。
0331デフォルトの名無しさん
NGNGnは (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)です。
これは基本的に身に付けておくべきテクニックの一つです。
0332デフォルトの名無しさん
NGNG0333デフォルトの名無しさん
NGNG0334デフォルトの名無しさん
NGNGそんなに速いの？ バイナリupｷﾎﾞﾝ
0335デフォルトの名無しさん
NGNGGCCでもBCCでもコンパイル出来るだろ
0336デフォルトの名無しさん
NGNGフサギコのコードより倍のサイズを列挙してるのに、３桁以上速い
0337デフォルトの名無しさん
NGNG0338デフォルトの名無しさん
NGNG0339デフォルトの名無しさん
NGNGエラトステネス同士でも実装次第で千倍くらい変わるんだ へぇ
0340Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG私も自分のコードを1000倍くらい高速化したですよ。
高速化よりも消費メモリが少ないほうが重要そうですね
Int32MaxIntまではがんがっても70MB程度は必要なのかな。
一昔前のものなら動かないし
Int64最大値までの素数値列を出すのはかなり遠いですね。
0341デフォルトの名無しさん
NGNGまずInt32MaxIntって書くより 2^31-1 って書いてくれた方が判り易いよ
サイズについては、2,3,5を除けば あと５M小さく出来るよ。
コードは大きくなるし、速度の効果は2割だから書きたくないけどね。
2^63-1の素数列を列挙するのは、世界中のHDを集めても容量が足りないでしょう
やるとすれば、2^64-1で指定された場所から 2^31個のフルイを作る事でしょうね
0342Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧ ／
ミ,,ﾟДﾟ彡 ＜ さらさらっとそういう計算できるのって
,;ﾞ ﾐ ＼ なかなか頭の切れがよいですね。
＠ﾐ,,,UUﾐ ￣￣￣￣￣￣￣￣￣￣￣￣￣
2^31-1 = 2147483647
2^63-1 = 9223372036854775807
2147483647ビットのフルイの箱が必要で
圧縮して1/3とかもうちょっとだけが減らせるから
8で割ってバイト数を出し
3で割って圧縮かけるということで
89478485.291≒90MB
同様に計算すると
9223372036854775807のフルイに必要なのは
384307168.ギガバイトですかね。
オンメモリで用意できるのはずっと先ですか...
0343デフォルトの名無しさん
NGNG例の定理が正しいとすれば
50年先ですから、生きてる間に見える可能性は高いかな・・・いや、CPU速度が追いつくのはさらに倍か
0344デフォルトの名無しさん
NGNG0345デフォルトの名無しさん
NGNGhttp://pc3.2ch.net/test/read.cgi/tech/983191866/910-911
が最速なんだってば。
0346デフォルトの名無しさん
NGNGとりあえず１０億まで計算させてみろ！ 話はそれからだ
0347デフォルトの名無しさん
NGNG(0～2^31) という条件だと、難しいんでは？
0348デフォルトの名無しさん
NGNG0349デフォルトの名無しさん
NGNG2^743-1 は素数ではありません
0350デフォルトの名無しさん
NGNG4.62686e+223
(・∀・)?
0351デフォルトの名無しさん
NGNG0352デフォルトの名無しさん
NGNGと問いたい。おっぱいを突付きながら問い詰めたい。
0353デフォルトの名無しさん
NGNGところで、132番目の素数って何のこと？
メルセンヌ素数は 40番目くらいを探索中でしょ
0354デフォルトの名無しさん
NGNG俺にも突っつかせろ
0355デフォルトの名無しさん
NGNG「132番目の素数さん」は数学板のデフォルトの名無しさん。
132番目の素数が743（名無しさん）であることから。
0356デフォルトの名無しさん
NGNG0357Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧＿__ ／
／ミﾟДﾟ,,ミ／＼＜ とりあえずupッときまつた
／|￣∪∪￣|＼／ ＼＿＿＿＿＿
|＿＿＿＿|／
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1035246186&res=10
これ動かしたら、10時間後には
0～int32最大までの素数列
ｽﾍﾟｰｽ区切りで数値の書いたテキストファイル
1GB分があなたの手元に！
0358デフォルトの名無しさん
NGNG素数xpとか。
0359デフォルトの名無しさん
NGNG1兆も計算出来るという事は 37bitの計算が出来るわけだし。
こんな方法はどうだろ？
上で出てる２，３の倍数を除く手法を拡張して、N迄のすべての素数の倍数を除くコードを
吐き出すプログラムを作るというのは
0360デフォルトの名無しさん
NGNG>>113が近い？
0361デフォルトの名無しさん
NGNG0362Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧ ／
_ ミ,,ﾟДﾟ彡 _＜ unsinedint最大まで求めるってのは
.=| |=U===U=| |= ＼いいかもしんない
| | .ﾐ ﾐ | | ￣￣￣￣￣￣￣￣￣￣￣￣￣
| |ﾉ∪''∪. | | しかし…もう篩いの容量が
劇的には減らないですねー
1兆は2^34では？
でも、私の試算ではメモリが715MB弱ほどは必要？！
どうやってんでしょ...
0363デフォルトの名無しさん
NGNG171億 7986万 では？
0364Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧ ／
_ ミ,, 彡_＜ ゲーム脳で頭が腐ったみたいです。
.=| |=ﾐ ミ=| |= ＼
| | ﾐ＠ ミ | | ￣￣￣￣￣￣￣￣￣￣￣￣￣
| | ∪''∪ | | 鬱だ。
| | | |
0365デフォルトの名無しさん
NGNG0366デフォルトの名無しさん
NGNG圧縮する時の係数を n bit目を 1/log(n) としたら、ほぼ完全な乱数になるのだろうか？
0367デフォルトの名無しさん
NGNGてめーああん？
カワイイじゃねえか、乳揉むぞｺﾙｧ
0368デフォルトの名無しさん
NGNG一気に計算する必要はないんよ。
過去ログにそういうアルゴリズムがあった。
0369デフォルトの名無しさん
NGNGDel使ってないからわからんのだがunsinedintってなに？
unsignedintの親戚かなにかか？
0371Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧ ∬ ／
ミ,,゜Д゜彡っ━~ ＜ 安心Edintを知りませんか？
＿と~,, ~,,,ﾉ_. ∀ ＼
ﾐ,,,,/~), │ ┷┳━ ￣￣￣￣￣￣￣￣￣
￣￣￣ .じ'Ｊ￣￣| ┃
￣￣￣￣￣￣￣ ┻
∫ ＿＿＿＿＿＿＿＿＿＿＿＿＿
∧,,∧ ∬ ／
ミ,,-Д-ノ,っ━~ ＜ ・・・ 俺も知らない・・・
＿と~,,, ~,,,ﾉ＿. ∀ ＼
.ﾐ,,,/~), .| ┷┳━ ￣￣￣￣￣￣￣￣￣￣￣￣
￣￣￣ .し'J￣￣|... ┃
￣￣￣￣￣￣￣ .┻
>>368
使わない所の古いはＨＤに退避させとくのですか？
速度とかの辛味で難しそうですね。
0372デフォルトの名無しさん
NGNGそのうちアイディア取り入れさせて貰います。
>>371
エラトステネスの篩いにおいて、ある数Nが合成数かどうか知るためには
√Nまでの素数リストがあれば十分です。
逆に言えば2からMまでを篩った結果（小素数表）があれば、それを用いて
M+1からM^2までを篩うことができます（拡張素数表）。
そして、拡張素数表の部分は一度に篩う必要はないです。任意サイズに
分割することができます。
ただし、
1. 分割すると、各分割の先頭でoffsetを定めるための除算が必要になるので
分割しすぎると除算のコストが高くなる。
2. 分割が少なすぎると、一度に篩うべき領域が大きくなるので、キャッシュが有効に
働かず、メモリーアクセスのコストが高くなる。
最悪の場合、swapが頻発してHDにアクセスしてしまうかもしれない。
という条件を考えて適切な分割サイズを定める必要があります。
これはマシンの一次,二次キャッシュのサイズにも依存しますし、微妙なところです。
とりあえず256KBあたりが無難な線ですが、多分最適サイズは他にあります。
分割された各領域の先頭でoffsetを定めるところだけ64bit演算を導入すれば、
32bitマシンでもあまり代わったことをしないで32bitMAXより上を篩うことも可能です
# ……最近某所で、キャッシュを有効にするための凄まじい方法も聞きました。
0373デフォルトの名無しさん
NGNGあのリンク貼った者です。まさか降臨なされるとは。
0374Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG.Λ,,Λ. ＿＿_
ミ；ﾟДﾟﾐ .||::::::::||
ミ つ___||_____||
|￣￣|__ﾐ―――――
`ー┬‐''
┴
>エラトステネスの篩いにおいて、ある数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が素数って判定した後は
それをどこかメモリに貯めておかなければならないのかな？？？
いや、、求めた瞬間にファイル出力したらいいのか...
0375Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG.Λ,,Λ. ＿＿_
ミ ,,彡 .||::::::::||
ミ つ___||_____||
|￣￣|__ﾐ―――――
`ー┬‐''
┴
私のコードは2147483647までの
素数篩いはメモリ上に構築可能なので(90MBもあるけど)
それを利用して
2147483647*2147483647=
4611686014132420609
までの値が素数かどうかはわりと、はやく判定できるのかな。
…それでもInt64の最大値 (2^63)-1 =
9223372036854775807
には届かないわけっすね。
それにしても、2147483647～4611686014132420609までは
一つ一つの値に対して、素数篩いに問い合わせなければいけないので
相当遅いことになる予感しま・・・・・
0376Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG> 逆に言えば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も抜きたいけど,,,
いったい、どうやるんだろかしら、、、、まだまだ奥深いです。
0377デフォルトの名無しさん
NGNG0378372 ◆2ZUH6PwhYk
NGNG>>376で仰ってる通りの感じです。
Rubyなんで読みにくいかも知れませんが、一応そのあたりのことが
http://idm.s9.xrea.com/factorization/eratosthenes.html
に書いてあります。
# この文も直さなきゃなー。
# 「3,5,7の倍数を除いても無駄」とか書いてあるし。
# 昔、試したところでは確かにあまり効果が上がらなかったんだけれど、
# このスレ見てる限りではどうも私の実装が腐ってただけみたい。
0379Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧ ／ 試行錯誤したり
ミ,,ﾟДﾟ彡 ＜ 実装したりして、いろいろ
,;ﾞ ﾐ ＼ わかってくるものっすね。
＠ﾐ,,,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を消したクラスを作成して
比較してみたのですが
メモリ消費量は減りますが
計算速度は高速化してないようでした。
0380デフォルトの名無しさん
NGNG高速化するなら >>324のようにしなくちゃね。
0～(2*3*5*7*11-1) で１と 2.3.5.7.11以外の素数のある個所を除いたテーブルを用意して
それを篩のビットを消す時に使うようにする。
0381Delフサ
NGNG2/3/5/7消しで高速化したら
∧,,∧ High(Cardinal)な素数ﾌﾙｲが
ミ,,ﾟДﾟ彡 ＜ 30分程度で計算できるように
ミ つ且~~ なったのですが、
ﾐ,,__ ヾ
⊂二二二UU二二⊃ それをIntToStrすると、
座して待ちすぎ？ 2GBのテキストファイルになって
それをファイルに生成するとこで
30時間程かかりました。
最後はこんなんであってるかな？
4294966997 4294967029 4294967087 4294967111 4294967143
4294967161 4294967189 4294967197 4294967231 4294967279 4294967291
0382デフォルトの名無しさん
NGNGしかし30時間もかかるもんなのか…
0383デフォルトの名無しさん
NGNG0384Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG～′,,,,,,,ミ,,ﾟДﾟ彡＜ 追加ってるから、めちゃ遅くなってるですね。
UU""" U U ＼
その辺りを高速化する気にはならなかったです。
なんか、D7からIntToStrがｱｾﾝﾌﾞﾗになったとかならないとか。
TBitsのﾒﾓﾘｲﾒｰｼﾞをﾊﾞｲﾅﾘファイルで保存できたら
面白いかもしれません。
(それでも数十MBのファイルはあまり扱いたくないかな。)
0385デフォルトの名無しさん
NGNG・２の倍数は素数ではない、つまり素数は奇数でなければならない
・素数（奇数）と素数（奇数）を足すと素数ではなくなる
・素数の１以上の倍数は素数ではない eg: 13*2=26 13*3=39->39/3=13
0386デフォルトの名無しさん
NGNGなんてね。>>385はうまいネタでも思いついた？
0387誰か
NGNG0388デフォルトの名無しさん
NGNG回線切って、首釣ってきます．．．
0389デフォルトの名無しさん
NGNG早くこのプログラムを提出しろ。
#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);
}
}
0390誰か
NGNG0391Warez
NGNG0392誰か
NGNG0393デフォルトの名無しさん
NGNGｵﾏｴｶﾞﾅｰ
0394デフォルトの名無しさん
NGNG`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)
0395デフォルトの名無しさん
NGNGdefine(`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)
0396デフォルトの名無しさん
NGNGAthlonXP 1800 メモリ 512MB で 2分50秒くらい
Pentium2 400MHz メモリ 128MB で 14分くらい
ってどうですか？
0397デフォルトの名無しさん
NGNG健闘してるんじゃない？ >>150といい勝負かも
ファイル出力込みの時間はディスクの状態によって結構変わる
測定前にデフラグをかけるとよろし
0398396
NGNGFreeBSDだからデフラグは関係無いみたいです。
あと、150とは全然比較になりません。
そもそも多倍長整数が扱えませんし。
多倍長整数ってすごく難しそうなイメージがあります。
0399デフォルトの名無しさん
NGNGなんだこりゃ?
0400デフォルトの名無しさん
NGNGhttp://www.crt.or.jp/~kokochi/sosu.htm
＞MMX Pentium 150 MHz のパソコンで、 0 ≦ 整数値 ≦ 4,294,967,295
＞の全素数 203,280,221個をカウントするのに、約 16 分を要する。
0401デフォルトの名無しさん
NGNG0402デフォルトの名無しさん
NGNG天進法かよ！
0403デフォルトの名無しさん
NGNGそれは知っているよ。
0404403
NGNG0405403訂正
NGNGなんでこんなバ化なんだ家の辞書（バ化だって・・・ＴOＴ）
0407デフォルトの名無しさん
NGNG「この前発表された公式」と言うのはインド人が見つけたアルゴリズムのこと？
0408デフォルトの名無しさん
NGNGそうかもしれない。あっちは素数一つを求める事が出来るとかか？
0409408
NGNGこのスレタイには
0410デフォルトの名無しさん
NGNG0411396
NGNGAtholonXP 1800 で 40秒台
Pentium2 400MHz で 3分30秒台
まで縮まりました。ファイル出力は無しです。
0412デフォルトの名無しさん
NGNGファイル出力ありの記録希望
0413396ではないが
NGNG0414396
NGNGAthlon で 35秒、
Pentium2 で 3分20秒、
ファイル出力ありだと、
Athlon で 2分ちょうど、
Pentium2 で 9分ちょうど
ぐらいでした。
0415396
NGNGファイル出力関連はめんどくさくて直してなかったので遅いです。
あと、n を p で割った答を a ,余りを r に代入するのに、
r = n - (a = n / p) * p;
とかしてたんですけど、普通に
a = n / p; r = n % p;
と並べたほうが速い(ほとんど変わらないけど)ことに気付きました。
コンパイラが最適化してくれるのでしょうか。
アセンブラを知らないので、内部的なことがよく分かりません。
0416デフォルトの名無しさん
NGNG除算命令は余りも同時に求めてくれるから、そのせいだと思います。
aを計算した段階で、rの値もレジスタに入ってるので。
でも、コンパイラがそこまで最適化してくれるんだ……。コンパイラは何ですか？
前にgcc 2.95で試したときはご丁寧に除算してくれてたけど。
私もソースきぼん。
0419396
NGNG人に見られることを意識していないので、死ぬほど汚たないです。
変数名一文字とか、変数使い回しとかいっぱいあります。
そのままだとファイル出力しないので、print_integerのコメントアウトを
二箇所はずしてください。fopenなのであらかじめprime.datというファイル
がないといけないかもしれません。ファイルは2G超えるので注意して下さい。
0421デフォルトの名無しさん
NGNG0422デフォルトの名無しさん
NGNG>>324 52秒
>>419 50秒
K6-2 400MHz
0423396
NGNG(n/6)*4+3 は (n*2-1)/3
(n/6)*8+1 は (n*4-1)/3
でもいいですね。
0424デフォルトの名無しさん
NGNG0x20000000+0x10000/8 でいいのかな？
余裕を取っただけでは？
0425396
NGNG{
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;
}
0426396
NGNGなんでなんだろう。
あと、ここのプログラムはどうなんでしょう。
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
0427デフォルトの名無しさん
NGNG高速にするなら
１、SetBit を展開して高速にする
２、２つの倍数消しを順にではなく交互にする >>308
0428396
NGNG{
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;
}
0430デフォルトの名無しさん
NGNG0431デフォルトの名無しさん
NGNGと言う訳で32以下の素数と、それ以上の素数を分けて篩いました
gcc2.95 オプション -O でコンパイルして K6-233(←CPU遅すぎ) で
2^32-1 までの素数を数えるのに4分弱でした
↓はそのソースです
無意味に構造体を使ってるので読みづらいですが…
http://tool-ya.ddo.jp/2ch/trash-box/file/20021129234010029.tgz
0432デフォルトの名無しさん
NGNG（ ﾟдﾟ）ﾎﾟｶｰﾝ
0433432
NGNG（ ﾟдﾟ）ﾎﾟｶｶｰﾝ
0434デフォルトの名無しさん
NGNG0435431
NGNGmain()の
for ( n = 1 ; n < 65536 ; n += 1 ) {}
nの値を1億に変えてませんか？
分かり辛いですが、このままで 2^32-1 までを求めてます
0437432
NGNGすいませんその時間は私が自分で作ったヤツのです(ウン子すぎ）。
（６n±1 を sqrt(6n±1)までの素数でひたすら割るもの）
2^32-1 までで4分っすか・・・早いですね。
0438他スレの297
NGNG100万まで1秒切れるというのはマジすか？？？
0439デフォルトの名無しさん
NGNG最適化のオプションをいじくるとか
0440123
NGNG0441デフォルトの名無しさん
NGNGここVB製。
http://f1.aaacafe.ne.jp/~zxrg/
0442デフォルトの名無しさん
NGNGAthlonXP 1800 で 20秒
Pentium2 400MHz で 2分11秒
ぐらいでした。
0443他スレの297
NGNG>>441のものには全然敵わない・・・くそ！！！
0445他スレの297
NGNG検索したけれども・・・ない。
0446デフォルトの名無しさん
NGNGエラトステネス
0447デフォルトの名無しさん
NGNGと ） | |
Ｙ /ノ 人
/ ） < >__Λ∩
＿/し' ／／. Ｖ｀Д´）/ ←>>444
（＿フ彡 /
0448432
NGNG次はエラテネシでやってみようかのぅ・・・
0449デフォルトの名無しさん
NGNG0450デフォルトの名無しさん
NGNGちなみに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;
}
}
}
//続く
0451450
NGNGfor(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;
}
0452450
NGNG//続き
for(i=2;i<=l;i++){
if(p[i]==1){
fout << i << '\n';
m=m+1;
}
}
cout << "素数は全部で" << m << "個です" << '\n';
fout.close();
return 0;
}
0453デフォルトの名無しさん
NGNG#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;
}
0454デフォルトの名無しさん
NGNG除算型の中でも遅い方だと思う。
0455デフォルトの名無しさん
NGNGCのコンパイラ持っていないので分かりません。
どれぐらい時間かかった？
0456デフォルトの名無しさん
NGNG0457デフォルトの名無しさん
NGNG今日会社で仕事中に思いついたいい方法を書くよ～ヒントだけど。
（ちなみにオイラはこの方法でしこたま短縮した）
１．「整数乗余」演算子を使わない（C/C++なら％、VBならMod）
２．エラストテネスのふるいをやる。
この方法でしこたま速くなる！！！
0458デフォルトの名無しさん
NGNGしこたま速くなるんじゃなくてしこたま遅かったんだろ。お前のが。
0459デフォルトの名無しさん
NGNGこれが２ｃｈの限界
0461デフォルトの名無しさん
NGNG0462デフォルトの名無しさん
NGNG>１．「整数乗余」演算子を使わない（C/C++なら％、VBならMod）
%ではなく / を使えということ？
0464デフォルトの名無しさん
NGNG本当に素数が出力しているのか自信がありません。
どなたか試していただけませんか？
#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;
}
0465デフォルトの名無しさん
NGNG0466デフォルトの名無しさん
NGNG0467デフォルトの名無しさん
NGNGつーことはリストに照らし合わせる必要がある限り、
無限のメモリが必要か。
エラトステネスで解こうとする場合、次の素数がどのくらいか予想できないと
どれほどのリソースが必要か分からない。
予想はできてるんですか？
0468デフォルトの名無しさん
NGNG漏れたちでエラトステネスより
オーダの小さいのアルゴリズムを
考え出せばいいのさ
0469464
NGNG勉強の為に作っただけなので、とりあえず１万桁でいいです。
0470デフォルトの名無しさん
NGNGってことは、おおよそ見当はついているのか。
力業が通じるかどうかってことなんだ。
0471デフォルトの名無しさん
NGNG0472457
NGNGだから、割り算をすると遅くなるんだよ。
発想の転換をしようや。
0473デフォルトの名無しさん
NGNG0474デフォルトの名無しさん
NGNGこのスレ全部読めよ
0475デフォルトの名無しさん
NGNG任意のn～mまでの素数を列挙する時じゃねえか？
0476デフォルトの名無しさん
NGNGフルイを作っていけば勝手に出来るだろ
0477俺（数学者崩れ）
NGNGVBでテキストファイルに入力しない場合は
100万以内の素数を調べるのに平均0.7秒台
テキストファイルに入力すると平均1.1秒台。
VC++（MFCを使わない）の場合は、
上のVB同じ条件で、ファイルに入力しないと平均0.2秒台
ファイルに入力すると2.2秒台・・・あれれ？？？
>>441のVB製に勝ててないが、俺は2の倍数を初めから除いていない。
ちゃ～んと2の倍数を消すところから計算スタートしてるの。
0478デフォルトの名無しさん
NGNGhttp://www.mersenne.org/prime5.txt (デカイのでナローバンドな人は注意!!)
0479デフォルトの名無しさん
NGNG0481デフォルトの名無しさん
NGNGVBはちゃんと最適化してるか？
0483デフォルトの名無しさん
NGNG0484デフォルトの名無しさん
NGNG2^32 ～ 2^32 + 2^31 のように大きな数を列挙する場合は
除算を使った方が良いだろ
0485デフォルトの名無しさん
NGNG0486デフォルトの名無しさん
NGNG0487デフォルトの名無しさん
NGNG黙ってろ表六玉
ここ更新したんやね
http://www.gt.sakura.ne.jp/~nyagy/integer/sosuu.html
0488デフォルトの名無しさん
NGNG#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;
}
}
0489488
NGNGwhile(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;
}
//かなり速いと思うが、どうよ？
0490デフォルトの名無しさん
NGNG324(関数部分は428でも可)ぐらい、短いんだからすぐ読めるだろう。
0491デフォルトの名無しさん
NGNGお前は何も解っていないんだな？？？
2と3の倍数を最初から除いておいて何の意味があるんだ？？？
だったら５も７も、１１も最初から除いておけよ。
アルゴリズム、って意味を知ってるか？？？お馬鹿ちゃん。
0492デフォルトの名無しさん
NGNGどのコードのどの「アルゴリズム」が324より優れているのか説明ｷﾎﾞﾝ
0493デフォルトの名無しさん
NGNG同意。
>>491
何で必死なの？
0494デフォルトの名無しさん
NGNGアルゴリズムをそっくりそのまま使う人ですか？
0495デフォルトの名無しさん
NGNGフルイの処理のループを一回最初っから実行しているのと同じ。
確かに処理として速くなるが、それならすべての素数を出した状態からスタートすればいい。
そう思った、小学5年の夏。
0496デフォルトの名無しさん
NGNG勘違いですね
0497デフォルトの名無しさん
NGNG意味不明
0498デフォルトの名無しさん
NGNG「アルゴリズム」の意味を理解していないデジドカの集うスレは。
0499デフォルトの名無しさん
NGNG馬鹿二人（藁
0500デフォルトの名無しさん
NGNGもう少し分かりやすく説明してもらえると・・・
0501デフォルトの名無しさん
NGNGたしかに2や3が最初から素数かどうかなんてコンピュータはわからないわけだから
アルゴリズムとしてはおかしい
けど実践的なのは事実
0502デフォルトの名無しさん
NGNGそれをアルゴリズムの間違いとするのは、おかしいだろ？
「アルゴリズムのクラス（or プロパティ）として、ユニバーサル性を欠く」
ということなら、わからないでもないが。
0503501
NGNG○ それをアルゴリズムがおかしいとするのは、間違いだろ？
0504502
NGNG0505495ではないが
NGNG追求するのではない。
２と３の倍数を初めから除いたアルゴリズムと、そうではなく
2から始めて3の倍数を消した後から、この二つのアルゴリズムを比較して、
速い方が優れているアルゴリズムなんだよ。
アルゴリズムとはそういうものなんだ。
0506デフォルトの名無しさん
NGNG2の倍数、3の倍数を省けば、メモリ使用量は 2/6。メモリ使用量は 4/6 減る。
5の倍数も省けば、 8/30。さらに、2/30 減る。
7の倍数も省けば、 43/210。さらに、13/210 減る。
11の倍数も省けば、 339/2310。さらに、134/2310 減る。
効果は徐々に薄くなっていくが、計算量は増えるから逆に遅くなる。
アルゴリズム的に無意味か知らんが、5の倍数くらいまでなら明らかに速くなるよ。
言いたいことは分かるが、小手先というにはあまりに効果的。
エラトステネスってあんまり工夫できないから、こういう事するしかないのよ。
0507デフォルトの名無しさん
NGNG意味不明な言葉で誤魔化さないようにしましょう。
0508デフォルトの名無しさん
NGNG速い方が必ずしも優れているアルゴリズムでないことはわかってます？
もちろん速度が最重視される分野ならばそれで良いことも多いのですが。
上のほうで述べられていましたが、求めた素数をどのように格納するか、
すなわち素数を求めるアルゴリズムでは、記憶容量の問題も大きい。
したがって予め2と3の倍数を除くアルゴリズムは、
速度と記憶容量の両面で優れていると言える。
0509デフォルトの名無しさん
NGNG素数を最初から知っているというのはおかしいということです。
だから素数テーブルを最初に用意したら
一番早いと>>495も言っている
まあ、ぶっちゃけ何でもいいよｗ
0510デフォルトの名無しさん
NGNG予め2と3と5の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。
0511505
NGNGこれはアルゴリズムではなく、プログラムだろ。
0512デフォルトの名無しさん
NGNG予め2と3と5と7の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。
0513デフォルトの名無しさん
NGNG小手先のテクニックを追求して、アルゴリズムに反映させるから、
より速く・優れているアルゴリズムができるのでは？
0514デフォルトの名無しさん
NGNG予め2と3と5と7と11の(以下略
0515デフォルトの名無しさん
NGNG2はともかく大きな数になると取り除くのにも色々方法がでてくる
0516デフォルトの名無しさん
NGNG単にユニバーサルかそうでないかの問題。
ユニバーサル性を重視するなら、「素数の定義」しか使ってはいけない。
しかし、多少のユニバーサル性を欠如させても、それ以上の効果があるならば、
分野によってはそのアルゴリズムの方が優れているといえる。
特に素数を求める場合は、2や3,5の倍数を取り除くことは当たり前にできる上に、
素数を求める目的から、その程度のユニバーサル性は必ずしも必要ない。
0517デフォルトの名無しさん
NGNG新しいアルゴリズムになってライセンス料支払わなくてよくなるかな？
0518デフォルトの名無しさん
NGNG2や3,5の倍数を取り除いてもアルゴリズムは同じです。
0519デフォルトの名無しさん
NGNG0520506
NGNG0521デフォルトの名無しさん
NGNG2や3や5の倍数を当たり前に取り除けるのは何故ですか？
2や3や5が素数だからですか？
2や3や5が素数であることを求める処理を省いていいんですか？
0522デフォルトの名無しさん
NGNGgif が問題になるのは LZW (＞ LZ78) を使っているから。
従ってLZWさえ使用しなければ問題ない。
しかし、LZWを別のアルゴリズムに置き換えたgifはもはやgifではない。
（一応、LZWを使わずにgifを実装できるが、遅すぎて使いもにならない）
0523デフォルトの名無しさん
NGNG面倒だから作るのいやなんですよｗ
0524デフォルトの名無しさん
NGNGhttp://petitmomo.com/mm/
ここがちょっぴりエッチ系のめぐが運営している出会いサイトです。
もしよかったら使ってみて、、、
ヨロシクです。
めぐ(^o^)-☆
0525デフォルトの名無しさん
NGNG多分>>516のいいたいことは、ユニバーサル性がどこまで重視されるか、の違いだけ。
立場が違えば解が違う。それだけ、だと思う。
0526デフォルトの名無しさん
NGNG素の状態からの素数探索を追求する人も
ひたすら爆速素数列挙を目指してる人も
ﾏﾀｰﾘしませうヽ( ´ー｀)丿
2と3の倍数を除外する以外にも過去ﾛｸﾞではいろんなテクニックが使われてるし。
0527デフォルトの名無しさん
NGNG素数じゃないのを求めてそれを省くとかするアルゴリズムはどう？
0528デフォルトの名無しさん
NGNGそれがエラトステネスの篩なわけで・・・
0530デフォルトの名無しさん
NGNGしね
0531デフォルトの名無しさん
NGNG人間の知識を与えるアルゴリズムを非ユニバーサルというらしいですね。
0532デフォルトの名無しさん
NGNG既にsusie用のgifプラグインとかそうしてる。
0534デフォルトの名無しさん
NGNG5の倍数も省けば速くなるかも知れんが、劇的に速くはならない。
ただ、メモリ一発でやっているので限界があるし、速くない。
だから、分割して篩うことを考える。
すると、分割されたメモリが一周するごとに計算が必要になる。
差がつくとしたらそこ。ほとんど小手先の塊みたいなもんだよ。
0535デフォルトの名無しさん
NGNGたしか>>419も分割してた気がするけど…
0536デフォルトの名無しさん
NGNG○ 分割しないエラトステネスの基本形
でした。
0537デフォルトの名無しさん
NGNG人間の知識っていうかこの場合は答えだからなぁ。
答えを入れれば答えを出すのが速いのは当たり前だし。
0538４８８
NGNGオイラのも入れろ！！！
0539デフォルトの名無しさん
NGNG分割してないじゃん
0540デフォルトの名無しさん
NGNGここの「アルゴリズムの基本」ってところとその証明、残念ながら
厳密には間違ってるよｗ
0541デフォルトの名無しさん
NGNG行く先々にあらゆる人材を送り込み、偶然を装っては
チンケな猿芝居やコザカしい罠、悪質な嫌がらせを次々と仕掛けてくる。
その、あまりにも回りくどく分かりにくい嫌がらせの手法で、
実際、気付くのに五年以上かかった。普通はまさか？と思うものだ。
だが偶然ではなかった。全て計画的に仕組まれたものだった。
あくまでも偶然を装ってである。何とも白々しく腹黒く悪質で陰険なことか！
こっちが気付かない、或いは知らん振りしてると、しつこく睨み続けてくる。
こっちが気付き不快感をあらわにすると、知らん振り。
頭にきて攻撃すると、散々自分から仕掛けて来ておきながら、
いかにも自分が被害者ぶるのである。
たとえ地元から遠く離れていても、である。
前以って嫌がらせを組織や会場にに潜り込ませたり、
あらかじめ通過地点に嫌がらせを配置・待機させる事もある。
一体奴らは何がしたいのか？気に入らないならダイレクトに来い！
被害妄想と思うかもしれないが、そうする事で
今までの不可解な出来事の全てにおいて、つじつまが合うのである。
偽善者という言葉は奴等の為にある。
学会のあるクソ信者と一緒にいると、
必ず初対面の人間からも頭ごなしに白い目で睨まれる。
明らかに年下の人間も俺を見下した目で見ている。
「あいつはロクでもないガキだ！」とでも吹いて回ってるんだろう。
表面上は親切ぶっていても、裏で糸を引いているのは奴等である。
正に偽善者と呼ぶに相応しい。
いつでも助けてやるよ！と言いながら、足を引っ張っているのは奴らだ！
偽善スマイルの裏では、腐ったはらわたがドス黒く渦巻いている。
学会の人間に心を開いてはいけない。
自分の知らない同一人物が目の前に度々現れたら要注意である。
0542デフォルトの名無しさん
NGNGお見事な縦読み
0543475==484==486
NGNGnからmまでの素数を求める時に篩を始める位置は
√n未満の素数(p)の場合は
((n-1+p)/p)*p
√n以上√m以下の素数(p)の場合は
p*p
で>>485で列挙範囲と言ってるのだから
最初から2・3・5等の素数を省くのに必要な除算は関係無い
要するに、これでは除算は√n以下の素数1つにつき1回除算が必要なのに
>2、3回除算使ってるな
と言ってる>>485は分かってない
つーか、それが分からないのなら、お前が黙ってろや>>487
0544Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNG∧,,∧∩ ／
頒ﾟДﾟ；彡＜ 除さん、いらんのですかい！
,;ﾞ⊃,ｼﾞ ＼＿＿＿＿＿
～ﾐ ,,○
∪ しらかた。
なんかｺﾑｽﾞｶな話ばかりでよくわかなんですが…
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;
あと、略
0545デフォルトの名無しさん
NGNGそれではお手並み拝見。
0546デフォルトの名無しさん
NGNG任意のnからmまでの範囲の素数を列挙するのに
除算は１回必要ですが、それに対して
>>485が>あぁ、確かに2、3回除算使ってるな＞範囲列挙
と書いてるので分かって無いと書いただけで
2・3・5等の素数を、省いて篩う場合には必要です
と言っても、そのコード読めないので
そのコードが正しいかは分かりませんが…
0548デフォルトの名無しさん
NGNG分からないと言いつつも分かったかも…
前の3を省いた時に使ってたnと2nを交互に足してった奴を
7までの素数に拡大したバージョンですね
それは、最初の一回は必ず除算を使いますし、省けませんね…
0549Delﾌｻｷﾞｺ ◆A6VzDeLphI
NGNGｷｭﾋﾟｨｨｨﾝ + ／
∧,,∧ ＜ よくわかりますた
ミ,, ﾟДﾟミ . ＼>>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まで
篩いに落ちるのを、目で見てソースに落とすのを
考えると鬱るので、まだやってません。
0550デフォルトの名無しさん
NGNGその部分を自動で適当に作ってくれるプログラムを作るとか…
ついでに、そのリンク先ですが、確かに分かりやすいですけど
遅い原因はprintfもそうですが、やってる事にも無駄が多いですよ…
分割して篩いたい時は、まず√nまでの素数を普通に篩って配列にし
その配列を使って篩った方が早いです
0551デフォルトの名無しさん
NGNGchar 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;}}
0552551
NGNG分割して篩うためのサンプルを書きました
適当に書いたので2の倍数も篩ってますが小さい素数を対象から外して
無駄(下から3行目のmod[i]-=sizeとそのwhileの条件等)も省いていけば
それなりに高速になると思います…が
>>426のリンク先が、マジで早いですよ…
バグがあるのか仕様なのか、2^32-1までの素数は篩えませんでしたが
2^32-10位の数で篩った時の早さは、自分が手を尽くせるだけ
尽くしたものに比べて2.5倍程早かったです(両方とも出力なし)
多分switchとcaseを連発して、7以下の素数を除外すれば
その差をかなり縮められると思いますが…
まぁ、>>426を試して、やる気を無くさなかった方は頑張ってみて下さい
0553デフォルトの名無しさん
NGNGそれは、その部分を関数にして処理しようとするからそうなるんで、
高速化したいなら配列 を作って状態遷移型に処理させるといい
その引数は、 a*b 実際には n=aでn:=n+b 繰り返しの格好をしてる訳でしょ？
そして、 aもbも 2,3,5,7 の倍数は含まない だから その差は 2310毎に繰返す
差を予め計算した配列を用意してやれば除算は必要ないよ
0554デフォルトの名無しさん
NGNG「乗算は加算の繰り返し、除算は減算の繰り返し」なので突き詰めれば
除算部分を別の等価のアルゴリズムに摩り替えることは常に可能なわけで…。
まあ面倒だからお手軽な組込除算命令を使うよね。普通は。
けど２や４の定数で常に乗除算するなら等価のシフト演算に置換する
くらいのテクは常套手段かと。＃“除算命令の抽象化”をやめてしまう
ようなものかな？それに「奇数か偶数（２の倍数）か」のふるいなんて
「x & 1」で解かるんだから置き換えなくちゃ損だよね。
余談の余談；
アセンブラレベルで悪いけど、PentiumのＤＩＶは表引きアルゴリズムをCISCに組みこんだ
ものなので演算コストが読みにくいんだが、RISC系の場合はそのへん割り切ってて
演算有効ビット数+α=実行クロック数くらいの演算コスト。
例えば……。SuperHなどは“必要精度(ビット数)分、(１回１ビット精度の)ＤＩＶを繰り返せ”と
いう素敵なアセンブル仕様なので、８ビット精度なら８回だけ、16ビット精度なら16回だけ、
ってふうに最適化することで演算コストを大きく切り詰められるんだよな。(´д｀;
閑話休題;
>>549
> 2*3*5*7*11で、2310まで
> 篩いに落ちるのを、目で見てソースに落とすのを
> 考えると鬱るので、まだやってません。
Perlerみたいなことを言うけれど…、そのソース(てか素数源ふるい表)自体を
プログラムに作らせちゃったほうが早くて正確じゃないですか？(´・ω・｀)
初期化段階で*11までの表を計算させちゃって、あとは2310の倍数単位
ループ内で、例外をふるってく…と。
＃この手だと13までは苦でなさそう。
0555デフォルトの名無しさん
NGNG一昔前は >>554の通り 除算は遅かった。
その頃は、 a/b で bが素数程度に連続して除算するならニュートン法を使う
なんて手も有効だった。
0556デフォルトの名無しさん
NGNGnまでの素数を求めたい時に必要な素数は√nまでの素数p
それらの各素数pがマークを付け始めるべき位置はp*p
だから、その最初の位置を決める時にp/2310の除(余)算が必要なんだって
0557デフォルトの名無しさん
NGNGpublic 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;
0558デフォルトの名無しさん
NGNGwhile(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;
}
0559デフォルトの名無しさん
NGNGcurrentBaisuu = 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;
}
}
0560デフォルトの名無しさん
NGNGアルゴリズムは
6までは最初から用しといて
30を目指して
(1または5)+6 *n()
の数に対してチェックしていく
30になったら
つぎは210になるまで
(1,7,11,13,17,19,23,29)+30*n
の数に対してチェックしていく
それを永遠に繰り返していくかんじ
速さは調べてないけど
テーブル自動化を目指した
0561デフォルトの名無しさん
NGNG正しいと思うが間違ってたらスマソ
0562デフォルトの名無しさん
NGNGただバグがあって、でかい数（2^32 -1）までやるとうまくできない？とか・・
ふるいは使ってないので誰かふるいを組み合わせて試してほしいです。
ちなみに自分はCがだめだめな学生なんで、ついでに誰かCで試して。ｗ
0563アフォ学生 ◆ZrbomZ0t3.
NGNGさびしいよ～～
さびしいからトリップ付けましたｗ
もしかして激しくガイシュツ？
そいつはｽﾏｿ
0564548==556
NGNGと言いつつ分かってなかったです(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'に保存
のように、分割した方が、篩いも圧縮も早くなります
(もちろん分割した事によるロスも馬鹿には出来ませんが)
と言う訳で、長くなりましたが、頑張って下さい
0565デフォルトの名無しさん
NGNGしかも早いし
0566デフォルトの名無しさん
NGNG削除対象アドレス：
http://pc3.2ch.net/test/read.cgi/tech/1018657457/541
削除理由・詳細・その他：
４．投稿目的による削除対象
５． 掲示板・スレッドの趣旨とは違う投稿
コピペ荒らしだと思われます。議論の妨げになるので
削除お願いいたします。
54 名前：削除屋つまようじ ★ 投稿日：02/12/16 20:33 ID:???
>53 縦読みしつつ流してください
0567デフォルトの名無しさん
NGNG0568デフォルトの名無しさん
NGNG一億やるのに13秒で早いだと？
これが、こんなに遅いのはjavaを使ってるからでも無ければ
テーブルを自動化したからでも無い
chkSosuu()で、除算で素数判定してるからだ
もう少しコードを読んでから、早い遅いを語ってくれ
0569デフォルトの名無しさん
NGNG0571デフォルトの名無しさん
NGNGあほな質問でごめんちゃい。
0572デフォルトの名無しさん
NGNG#include <stdio.h>
#include <stdlib.h>
#include <malloc..h>
多分。
0574571
NGNG573は無視して・・・。
0575デフォルトの名無しさん
NGNGなんだそれは食い物か
0576デフォルトの名無しさん
NGNG0577デフォルトの名無しさん
NGNG0578デフォルトの名無しさん
NGNGAthlonXP 1800 で、やっと426 に勝ったと思ったら
Pentium2 400MHz では全然負けてました。
426と比較すると
Athlonで 11秒 と 12秒 (ほとんど変わらない)
Pentiumで 1分23秒 と 55秒 くらいでした。
http://tool-ya.ddo.jp/2ch/trash-box/file/20021222173653053.c
0579デフォルトの名無しさん
NGNG頑張りましたね…
でも、出来れば少しだけでもコメントをつけるなり
影響の少ない範囲で、main()のコードを複数の関数に分割して欲しかった…
0580デフォルトの名無しさん
NGNG0581578
NGNGそうですね。少しでも速くすることを考えてました。
分割したエラトステネスの篩で3、5、7の倍数を省いています。
√n未満の素数(p)の場合は
((n-1+p)/p)*p
√n以上√m以下の素数(p)の場合は
p*p
から篩っています。すごく普通のエラトステネスの篩です。
滅茶苦茶汚たないのは、331に書いてあるデジタル微分解析法とやらで、計算量を減らしているからです。
こんなあほなことするより、真面目にアルゴリズムを考えたほうがいいですね。
0582578
NGNG0583デフォルトの名無しさん
NGNG素数の列挙の場合、マジメにアルゴリズムといってもフルイの範疇でしかないから
その手のあほな手法をチマチマくみたてあげるしか無いんだよね
0584578
NGNG(ファイル出力ありの場合は変わりませんが)。
そして、set_bitのレベルにまでデジタル微分解析法を適用したら0.4秒ほど縮まりました
(そのせいでコードの長さが3900行を超えたのに、効果が少なくて悲しかったです)。
最終的に AthlonXP1800で8秒ジャスト、Pentium2 400MHzで59秒くらいになりました。
改良の余地が無いとは言えないのですが、そろそろ限界です。なのに426に勝てない。
>>583
素数公式ページみたいな所のリンクのプログラムの篩いの所に一つだけエラトステネス
でないものがあるのですが、あれはどうなんでしょう？
ある素数(p)が二つの平方数の和で表わすことができることが、 p = 1 (mod 4)と同値である(2は例外)ことを
利用しているようなのですが、そういう方法もあるみたいですね。
0585デフォルトの名無しさん
NGNG2*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
ホントだ
激しく亀レスだけど
Σ(ﾟдﾟlll)ｶﾞｰﾝ
そのうち見直して修正しまつ。
0587デフォルトの名無しさん
NGNG速いかなあと思ったのですが、逆に遅くなりました。そういうものなのでしょうか。
あと、分割した篩を埋めていって、はみ出た時に場所とタイミングを記憶しておけば、
全く割り算を使わずに済むかなあと思いました。
あと、良く知らないのですが、Mathematica とかいうのがくそ速いらしいですね。
0588デフォルトの名無しさん
NGNGメモリアクセスを行ってるから、配列を使うとそれだけ
キャッシュミスが増えるって事じゃないのかな
割算そのものは重いといっても加算減算とは別に平行して実行されるから
頻度にさえ気をつければ、除算を使ってシンプルになるなら使った方がいい。
0589デフォルトの名無しさん
NGNG篩のサイズをかなり小さくしたら、二次元配列のほうが速くなりました。
でも、二次元配列のサイズに比べてかなり小さくしないといけなかったので、なにか違うような。
メモリをたくさん使っているときは、配列から値を取り出す動作そのものが遅いと考えれば、辻褄があうのかな。
割り算の頻度は結構高いのですが、配列から値を取り出す動作が遅いとなると、計算したほうが速いのかもしれません。
0590デフォルトの名無しさん
NGNG多段パイプラインなCPUの場合、例えば割り算の
結果が得られるまでに５クロックほど掛かるなら、その間に
別の１クロックで済む命令を４個実行させられたりする。
「奴からメールの返事がくるまで暫く掛かるから、その間に
別の奴へのメールも書いておこう」みたいなのと同じこと。
待ち時間の高そうな結果依存部分が集中しないようしてやれば、あとは
コンパイラやCPU自身が判断して真の命令実行順序を考えてくれると思う…。
a = p[ q / s ]; b += d;
↓
i = q / s; b += d; a = p[i];
みたいな？意義低そうだが。
(i を register int 宣言したら効果的？)
0591デフォルトの名無しさん
NGNGなるほど。そういうことも考えながら書くといいんですね。
エラトステネスというアルゴリズムは工夫する余地があまりないので、
プログラミングテクニックを追及していくしかないですね。
割り算なしで一から書き直してみたのですが、やはり少し遅くなりました(書きかたが悪いのかもしれませんが)。
その代り大きな数を扱わないので、10^11くらいまでなら計算できるようになりました。
10^10まで450052511個を数えるのに
AthlonXP1800 で 21秒
Pentium2 400MHz で 4分5秒
10^11まで4118054813個を数えるのに
AthlonXP1800 で 4分20秒
Pentium2 400MHz で 45分52秒
くらいでした。
Pentium2のほうではメモリのサイズを減らせばもっと速くなると思うのですが、
メモリのサイズを減らすと計算結果がおかしくなるというバグがあるので今は無理でした。
double型を使えばもっと大きな数まで計算できると思います。
0592591
NGNGファイル出力無しで比較したかったので、
primes 9999999900 10000000000 とかしてみたのですが、一瞬でした。
範囲が狭いときは篩を作らずに一つ一つ素数判定しているのならば納得できるのですが。
結局、
time (primes 0 4294967291 > prime.dat)
で比較してみたのですが、自分のより3倍ほど速かったです。
ファイル出力部分は作り込んでないので、その差もあるかもしれませんが。
とりあえずソース読んでみます。
0593デフォルトの名無しさん
NGNGがんがってくだちい。自分は>>590を試してみようと思ふ
0594デフォルトの名無しさん
NGNG0595デフォルトの名無しさん
NGNG会員専用？
0596デフォルトの名無しさん
NGNG0597デフォルトの名無しさん
NGNG細かいミスがたくさんあって全て直したつもりなのですが、少し自信がありません。
なにかおかしいところがあったら、教えてくれるとありがたいです。
引数以下の素数の数を出力します。引数は30で割って桁溢れしない数にしてください。
速さにはあまり期待しないでください(そんなに遅くないと思いますが)。
http://tool-ya.ddo.jp/2ch/trash-box/file/20030102235159180.c
0598597
NGNG上のとほとんど同じで申しわけないのですが、出力部分を作ってみました。
-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くらいまでの素数は見つかっているみたいですね。果てしない。
0599デフォルトの名無しさん
NGNG1Gh 256Mb で１時間かけてあるふたつの素数の積を
素因数分解をする場合には何桁の素因数分解ができれば優秀なプログラムと言えるのでしょうか?
0600デフォルトの名無しさん
NGNG普通に素因数分解をすれば、
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が素因数分解出来れば非常に優秀
0601デフォルトの名無しさん
NGNG64bitですかぁ 簡単にはいきそうにないっす。
気長にちびちびとやっていきます。
完成すればうpするのでまっててちょ。
0602597
NGNGその間普通にパソコン使っていたので正確には分かりませんが。
一晩かけて10兆まで計算させようとしたのですが、2時間くらいで終ってしまって
答えも合っていませんでした(たぶん格上げ関連のミスだと思います)。
あと、 long long intという型があるのを知ったのですが、これは使ってもよいのでしょうか。
移植性も考えるとdoubleを使ったほうがいいのでしょうか。ビット演算もできるので少し驚きました。
素数計算の実行時間が書いてあるページがありました。ぴんとこないけどかなり速そうですね。
今から計算しはじめるのと、少し待ってもっといいCPUができてから計算するのと、どっちが速いのかなあと思いました。
http://numbers.computation.free.fr/Constants/Primes/Pix/results.html
0603デフォルトの名無しさん
NGNGVB6.0で組んでいるんですが、100万までだと「個数勘定なし・出力なし・
２や３の倍数をあらかじめ消しておくというのも無し」で、平均0.21秒台です。
VB6.0だとこれが限界かなぁ。。。
みなさんはどうです？
0604603
NGNG「API関数も使わない」で、です。
0605デフォルトの名無しさん
NGNG環境示せ。過去ログにVBの事も出てたよ。
0606603
NGNGって書いてある（すんません・・・PCの環境については良く知らないんです・・・。）
ちなみに>>441のリンク先のものよりも速いですが・・・オイラのPCだと。
0607デフォルトの名無しさん
NGNG0608デフォルトの名無しさん
NGNGボタンをチェックすれば出力無しに出来るよ。
0609デフォルトの名無しさん
NGNGそれでもTEMPフォルダに出力してるようだが
0611デフォルトの名無しさん
NGNGがんがってね。応援するよ
0612デフォルトの名無しさん
NGNG他のアプリを全て終了してから、出力無しで「2^31-1」まで
計算させようとするとおれのPCではメモリ不足のエラーが出る。
そういうことを考えると・・・・恐らく2,3の倍数を初めから
消しているのかな？
0613597
NGNG0614デフォルトの名無しさん
NGNGhttp://numbers.computation.free.fr/Constants/Primes/pixtable.html
ここに素数の個数を数え上げた年代が書いてあります。
1985年には分散コンピューティングも無いだろうし、スーパーコンピュータを使っているんでしょうか。
当時のスーパーコンピュータの性能はどれくらいなんでしょうか。4*10^16まで求まる気がしません。
0615デフォルトの名無しさん
NGNGdjb氏って、それって何処にあるの？
0616pascal
NGNG2^31 未満の素数の全リスト。
適当に作ったやつだから２日くらいかかったけど。(Pen!!! 1.00GHz)
使った方法は、既出だけど
１．sqrt(2^31)未満の素数リストをふるいで作る
２．それを読み込んで、新たな数ｎをaqrt(n)未満の素数で割る
ソース発掘中・・・。
＃それとは別に１０万個ずつ素数を見つけてファイルに書き込むものもあり。
＃ともに暇ならUPしますが。
0617デフォルトの名無しさん
NGNGhttp://cr.yp.to/djb.html
ここの primegen ってとこです。
0618デフォルトの名無しさん
NGNGうｐきぼーん
0619pascal
NGNG発掘・実行してみたらとてつもなく遅かったので自主規制です(^-^;
てか恥ずかしくて見せられん。
ふるいも使わずビット演算とかもせず、ゆえに割り算ばっかりしてるので１０００万までで１０秒弱かかります。。。
似たことやってる人がいてちょっとほっとしました(^-^)
意味のない数値計算はよくやるので、自鯖があったらいろいろＵＰしたいのだけど。
円周率１２０億桁とか(ぉ
拾いものです。正しいのかどうか比較対象がないのが痛いけど。
駄文＋横道＋長レスすまそ。
0620デフォルトの名無しさん
NGNG3.14
というのは円周率の定義でないと最近おもいつきはじめている。
0621デフォルトの名無しさん
NGNG一兆まで 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氏のは謎なのでそこに希望があるかもしれません。
0623デフォルトの名無しさん
NGNG頭大丈夫？
0624621
NGNGだから速かったみたいです。djb氏のとは比較にならないくらい遅いです。
32ビットの範囲でも long int と long long int では割り算の速さが全然違いますね。
0626デフォルトの名無しさん
NGNG小学校で習わなかったの?
0627デフォルトの名無しさん
NGNG一定期間でログは消しますです。
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
いずれは。
0628デフォルトの名無しさん
NGNGあるネット関連会社の社長は、
「いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう」
と証言する。
2ちゃんねるが判決によって力を失った場合、
資金提供の打ち切りも予想される。
http://ascii24.com/news/reading/causebooks/2002/07/01/636911-000.html
0629デフォルトの名無しさん
NGNG円の面積÷半径の２乗
0630デフォルトの名無しさん
NGNG節穴はマジ書き＞通報
ってルール駄目？
警察忙しくなりそうだな。
0631デフォルトの名無しさん
NGNGあまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう
0633デフォルトの名無しさん
NGNGつーか検索しろよ
0634デフォルトの名無しさん
NGNG２ちゃんねるのお勧めな話題と
ネットでの面白い出来事を配送したいと思ってます。。。
===============================読者数： 138720人 発行日：2003/1/9
年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。
そんなわけで、年末に予告したIP記録ですが実験を開始しています。
「２ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。
んじゃ！
────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
0635デフォルトの名無しさん
NGNGそれが算数の授業での説明なわけね。
2chねらーに聞きたかったんだよう。
0636デフォルトの名無しさん
NGNG半径1の円を内接、外接する3角形で近似する。
極限をとれば、同じ値に収束して、その値が円周率。
0637デフォルトの名無しさん
NGNGだったら>>633が正解。
ム板的に、円周率の近似計算アルゴリズムを聞きたいなら別だけど。
0638デフォルトの名無しさん
NGNG個人的にはエロっぽいギャグも誹謗中傷ととられたら俺もIP記録はやばいな（；´Д｀）
0639デフォルトの名無しさん
NGNG録音とか（盗聴も）
してていいです。
只、そのノイズも国家機関に分析されます。
2分後に掛けます。
自己紹介と、一般の世間話をしたいと思います。
最初に確認したいのですが（深夜で遅いし。用件もあっさり、こってり。一見だし）
「私」青少年が色々と危機的なんです。
「早急に」＋、前向きに
色々と検討して下さいますでしょうか。
私は18歳です。其方のプロフィールを簡単に今お願いします！ありがとう。
0640デフォルトの名無しさん
NGNG0641デフォルトの名無しさん
NGNG0642デフォルトの名無しさん
NGNG削除人の個人個人の判断じゃだめ。
0643デフォルトの名無しさん
NGNGの間違いだと思われ。
IP取ってない方が珍しいし。
0644デフォルトの名無しさん
NGNG0645デフォルトの名無しさん
NGNG0646デフォルトの名無しさん
NGNG小1時間経ちましたがまだ腹痛は来てないので大丈夫そうです。
あずき缶と白味噌、里芋を買って正月に備えます。ﾋﾞﾊﾞ独り身。
0647デフォルトの名無しさん
NGNG0648デフォルトの名無しさん
NGNG注意：ここは素数列挙アルゴリズムスレです
0649デフォルトの名無しさん
NGNG0650デフォルトの名無しさん
NGNG0651デフォルトの名無しさん
NGNGhttp://dailynews.yahoo.co.jp/fc/computer/2channel/
0652デフォルトの名無しさん
NGNGIPの記録が抑止にもなるなら、削除系の板のリモホ表示をやめて
みるのはどうでしょう。
依頼者のホストを削除板以外の板に晒されることもないでしょうし。
0653デフォルトの名無しさん
NGNG管理人は「逝ってよし」もダメだと言うのか！？
0654デフォルトの名無しさん
NGNG0655デフォルトの名無しさん
NGNG２ちゃんねるのお勧めな話題と
ネットでの面白い出来事を配送したいと思ってます。。。
===============================読者数： 139038人 発行日：2003/1/10
なにやら、連日メルマガだしてるひろゆきです。
そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。
重くなって落ちたりしてもご愛嬌ってことで。。。
んじゃ！
────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
0656デフォルトの名無しさん
NGNG0657デフォルトの名無しさん
NGNG0658デフォルトの名無しさん
NGNG0659デフォルトの名無しさん
NGNG復讐的なﾁｸﾘもなくなるのだぞ！！
0660デフォルトの名無しさん
NGNGIPなんか始めから記録してるだろよ
0661デフォルトの名無しさん
NGNG0662デフォルトの名無しさん
NGNG0663デフォルトの名無しさん
NGNGそりゃそうだ(^_^;)まあハッキングと強盗は区別するってことで
２０レス分くらい読めよ(^_^;)
どこまでＯＫなのかわかってたら訴訟で負けたりしません(^_^;)
なるほど(^_^;)
0664デフォルトの名無しさん
NGNG0665デフォルトの名無しさん
NGNG0666デフォルトの名無しさん
NGNG誤爆？
少女漫画かアニメ板から
0667デフォルトの名無しさん
NGNGメンヘルと言ってた女が実はシャブ中だった！！！
http://tmp.2ch.net/test/read.cgi/tubo/1042129878/l50
0668デフォルトの名無しさん
NGNG0669デフォルトの名無しさん
NGNG0670デフォルトの名無しさん
NGNGHackerの名を汚すな。馬鹿。
IPからメールアドレスだと？
馬鹿か。割り出せるのは契約者の接続アカウントだ
0671デフォルトの名無しさん
NGNG0672
NGNG0673山崎渉
NGNG0674デフォルトの名無しさん
NGNG0675山崎渉
NGNG0676山崎渉
NGNG0677デフォルトの名無しさん
NGNG0678デフォルトの名無しさん
NGNG0679デフォルトの名無しさん
NGNG巨大素数の計算式もうできたんでしょ＞？
0680デフォルトの名無しさん
NGNG0681デフォルトの名無しさん
NGNGロシアの数学者が何十年も前に考案しています。
0682デフォルトの名無しさん
NGNG0683デフォルトの名無しさん
NGNGがどうした？
0684デフォルトの名無しさん
NGNG0685デフォルトの名無しさん
NGNG$ 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です。
0686デフォルトの名無しさん
NGNG0687デフォルトの名無しさん
NGNG0688デフォルトの名無しさん
NGNGhttp://www.mcc.pref.miyagi.jp/people/ikuro/koramu/prime.htm
0689デフォルトの名無しさん
NGNG>N以下の素数の個数を示すのに、Nまでの数字を全部チェックする
>バカはいないだろ。
>（ルートNまでという意味ではない）
なんで、これで素数定理が出てくんの？
求めたいのは、およその個数ではなくて、正確な数でしょう？
およその数で良いのなら、最初から、そう書いてけよ
それとも、これで正確な数が出るとでも思ってるの？
0690デフォルトの名無しさん
NGNGそれより早いアルゴリズムはないんじゃない？
Nまでの数をふるいにかけて、
数え上げたほうがはやそう。
0692デフォルトの名無しさん
NGNG0693621
NGNG古い話ですが 621 の print_prime を書き直したら4000億あたりから621のほうが
djb氏のより速くなりました。しかし速いといっても微妙なのでなんとも言えません。
Pentium2 400MHz では621のほうが全然速いので環境によって結構変ってくるみたいです。
で、数論の入門書を見ていたら面白そうなことが書いてあったので引用してみます。
0694621
NGNGn番目の素数 Pn の単純な一般式はあるか？ (すなわち、与えられた
nに対してエラトステネスのふるいよりも楽に Pn の値を計算できる公式が
あるか？)
そのような公式は知られていないし、そのような公式はありそうもない。
一方、様々な Pn の「公式」を考案することはできる。これらのうち、あ
るものは Pn をそれ自身を用いて定義しており、従来知られていない Pn の
値を計算することができないので、ほんの興味をそそるものにすぎない。定
理 419 において例を与える。他のものは理論的には Pn を計算することがで
きるが、エラトステネスのふるいよりも実質的に多くの労力を払うことによっ
てのみ可能である。 その他のものはエラトステネスのふるいとなお本質的に
同等である。
要はエラトステネスが最良のアルゴリズムであるということが証明されてるみたいです。
0695デフォルトの名無しさん
NGNGもう消えてる？ それともYBBだから？
0696デフォルトの名無しさん
NGNG保存できない？
0697デフォルトの名無しさん
NGNG数学板にスレが立ってますよん
http://science.2ch.net/test/read.cgi/math/1006151996/-100
0698デフォルトの名無しさん
NGNG> 「数論入門I 」より引用します。
これって誰の本?
0699621
NGNGもう消えています。アップローダーだといつかは消えてしまうのでしょうがないです。
>>698
G.Hハーディ/E.Mライト 著
示野 信一/矢神 毅 訳 です。結構古い本です。
プログラム板的には「はじめての数論」も良いと思います。
プログラムを書く問題があったり、暗号についての話があったりします。
ただ証明は大体「数論入門I」のほうが分りやすかったです。
0700695
NGNGよく見たら、日付が1/8でした。
番号がそんなに違わないし、同じ話題が続いてるので、
少し前の公開かとカン違いしてました。
0701デフォルトの名無しさん
NGNG0702デフォルトの名無しさん
NGNG0703デフォルトの名無しさん
NGNG0704デフォルトの名無しさん
NGNG0705デフォルトの名無しさん
NGNGじゃあ、当分は定期的に保守しておくよ。できれば途中経過など聞かせておくれ。
0706デフォルトの名無しさん
NGNG0707706
NGNGダメだMAXが10^10を超えるあたりからcallocができないっす。
よってやめます。
メモリをケチることは重要っぽいです
1億くらいまでは正しく求められそうでした。
stdout だと遅いかと思われるのでリダイレクトして
#define MAX ???
に求めたい素数列の最大の値をいれてください
0708デフォルトの名無しさん
NGNGここに書いてあること分かる人いますか？
僕は英語苦手なのでよく分かんないんですけど、かなりレヴェル高い気がします。
あとdjb氏のより速いプログラム見つけた人いますか？
最近 primespeed で個数だけ数えてくれることに気づきました。
0709山崎渉
NGNG0710デフォルトの名無しさん
NGNG一応キャッシュ消えないうちに貼っときます。
とんでもなく速いですね。JAVAなのに。
0711デフォルトの名無しさん
NGNGエラトステネスの計算量は O(n*log(n)) らしいのですが、O(n^(1/2)*log(n))
で計算できるらしいです。dvi ファイルに詳しく書いてあります(僕は理解して
いませんが)。
>>694 との関連はよく分りませぬ。
0712711
NGNGParity of pi(n) ってとこです。
0713デフォルトの名無しさん
NGNGこれがループ回数を決定するから計算量はこの素数たちの個数で求まる。
で、素数定理よりその素数たちの個数が1/2 * n^(1/2) * log(n)個程度だから、
……でいいのかな？
0714デフォルトの名無しさん
NGNG今適当に考えてみたのですが単純にステップ数を数えると、
p <= √n 、 Σn/p ですよね。
Σ1/p <= log(√n) だから
O(n*log(n)) になるんじゃないのかな。
0716デフォルトの名無しさん
NGNG作ってみました。
ソース改良したり、アップしたり、リンク足したり、なにやってもよいと思いますが
いつ消えるか分りませんのでご注意。
0717711
NGNGの 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)) かかり、エラトステネスより効率悪いみたいですね。
0718デフォルトの名無しさん
NGNG0719山崎渉
NGNGﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
0720デフォルトの名無しさん
NGNG（盛り上げていこうぜ！！山崎渉なんかに負けんな～）
0721デフォルトの名無しさん
NGNG0722デフォルトの名無しさん
NGNG0723山崎 渉
NGNG__∧＿∧_
|（ ＾＾ ）| ＜寝るぽ（＾＾）
|＼⌒⌒⌒＼
＼ |⌒⌒⌒~| 山崎渉
~￣￣￣￣
0724磯引葦胃葦斡
NGNG0725デフォルトの名無しさん
NGNGすっかり落ち着いてますが
0726山崎 渉
NGNG0727デフォルトの名無しさん
NGNGhttp://www.msnusers.com/AmateurMath/primecountingfunction.msnw
0728デフォルトの名無しさん
NGNG今までの苦労はなんだったんだ ってくらい。
0729山崎 渉
NGNG│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
⊂| |つ
（＿）（＿） 山崎パン
0730デフォルトの名無しさん
NGNG0731デフォルトの名無しさん
NGNGn…適当な数 p…素数
0732デフォルトの名無しさん
NGNG0733デフォルトの名無しさん
NGNG0734デフォルトの名無しさん
NGNGtemplate<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ループの「番兵」が活かせなくなってしまうので、
何かよい方法はないかと思案しています
0735
NGNG0736デフォルトの名無しさん
NGNG偶数も含めて除算していくアルゴリズムが在るだろw
そろそろエラトステネスについては語りつくしたようだしテーマを変えてみないか?
次のテーマ "エラストテネスの篩い以外のアルゴリズムでどれだけ速くできるか?"
まずはウィルソンの定理あたりでw
0737デフォルトの名無しさん
NGNG判定用アルゴリズムで、こういうの考えました。
多分速くは無いけど、メモリはそんなに使わないと思います。
2～7の素数はデフォルトとして桁数が多い場合の処理を考えてみました。
たとえば８１３７の場合
もしこの数が素数でなければ、下１桁が１×７、または３×９の数字の積だと言うことがわかる。
そこで(１×７の計算は終わった物とします)
＿＿＿９
３） ８１３７
２７
８１１
３と掛けて下一桁が１になるのは７だから
＿＿_７９
３） ８１３７
２３７
７９
３と掛けて下一桁が９になるのは３だから
＿___３７９
３） ８１３７
１１３７
７
３と掛けて下一桁が７になるのは９だけど、３×９３７９はもとの数より大きいのでスキップ
つづく
0738デフォルトの名無しさん
NGNG＿___＿_９
１３） ８１３７
１１７
８０２
と言う感じに計算すると、
＿＿_７９
１０３） ８１３７
８１３７
となり、素数ではないことが分かる。
こんな感じで計算すれば、桁数が多くても網羅する範囲を絞れないでしょうか？
0739デフォルトの名無しさん
NGNG１３，１０３はどうやって決定するんですか？
１３，２３，３３，４３，５３… って１０の位を増やして全て計算するんですか？
0740デフォルトの名無しさん
NGNG(篩いなら一瞬だろうけど)
0741デフォルトの名無しさん
NGNG0742デフォルトの名無しさん
NGNG0743デフォルトの名無しさん
NGNG/ ,――――-ミ
/ ／ ／ ＼ |
| / ,（･） （･） |
(6 つ |
| ＿＿_ | ／￣￣￣￣￣￣￣￣￣￣
| /＿＿/ ／ ＜ なわけねぇだろ！
／| ／＼ ＼＿＿＿＿＿＿＿＿＿＿
0744デフォルトの名無しさん
NGNGsqrtを使わずにxについて解く事って出来ますか？
0745デフォルトの名無しさん
NGNGニュートン法などによる近似
0746デフォルトの名無しさん
NGNGx^2 * 2 + x * 44 + 43
x^x * 2 + x * 48 + 89
0747デフォルトの名無しさん
NGNGレスきてた。
やっぱりそこですよね・・・。
それなら、判別する数の下一桁が１，３，７，９の場合、下１桁が１，３，７，９の数で順番に割ってみるっていう風にしたほうが早いですよね。
下一桁が０，２，４，６，８の場合は偶数、下一桁が５の場合は５の倍数なので判別する数が２桁以上の場合、必ず素数にはならないのですぐ結論が出るし。
下一桁が１の場合素数でなければ下一桁が１×１、３×７、９×９の合成数
下一桁が３の場合 〃 １×３、７×９ 〃
下一桁が７の場合 〃 １×７、３×９ 〃
下一桁が９の場合 〃 １×９、３×３、７×７ 〃
これをどうにか利用できないかなぁ・・・
0748デフォルトの名無しさん
NGNGとりあえず二進法で考えて下さい。
割り算がしたいのなら多倍長計算スレへ。
0749デフォルトの名無しさん
NGNG300万で30秒まで行きました。
まだまだ未熟者です。
リンクのソースを読もうと思ったら、
ほとんどリンク切れしてしまっていたのですが、
誰か早いのを作っている方で、
もう一度リンクを張っていただけないでしょうか？
できればCでお願いします。
0750デフォルトの名無しさん
NGNG>>617
>>727 はどっかいったみたい。ソース持ってるけど。
0751デフォルトの名無しさん
NGNG1. 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;
これって結局何だったの？
0752デフォルトの名無しさん
NGNG0753デフォルトの名無しさん
NGNGありがとうございます
0754わむて ◆wamuteW7DE
NGNG（ .，‐ '´ ヽ-、_
／⌒）i ﾚノﾉ）)） ＼ヾヽ ／￣￣￣￣
／ヽ './人il.ﾟ - ﾟﾉｲ|/.ヾヾヽ＜ みる、みる、みるまらーーー！
ゞ （"....（ (ヽ ⊂)Yiつヽ） |'ﾉ | わむてさん、地球！
(" "ヽ＼.' く _ :|〉ヽ.ヽ| | ノ |
'( " ヽ＼し'ﾉ ヽ| |ﾉ ノ ＼＿＿＿＿
（＼ '("ヽ＼ |ﾉ
＼） '(（. " し″
0755デフォルトの名無しさん
NGNG言数μの儀環δ(μ)によって外数μ'/偶数は定位を持つ。(自明)
線形乖離により轍環はδによる写像σの約値を持つ。
轍環は無限順列を持たない為、輪位は定位と双対ではない。(μ'までも乖離される。)
律価をοとすると言群をMとし、単置換をπとすると、約値が相似単置換π'に相当し
∀{∀(∀σ , ∃π) ,∃π' s.t δμ=φ},∃ ο∈NM s.t δπο∽σπ'μ が言える
これを展開すれば、言数定理によって、乖離され、
δπμ'=φ となる為、補遊値は0になる。
自然数においてδの域数 ω(δ)=2,
πの弄数 Å(π)=2 であり、 ω(δ)Å(π)=4
補遊値=0だから4+0=4。
∴4以上の全ての偶数は2つの素数の和で表せる
0756デフォルトの名無しさん
NGNG自分が発見した素数の定理を使用して素数列挙プログラムを作成しています。
それで、コンソールアプリケーションしか作れないのでそれでDOSに素数を表示してるのですが、
PCが計算して出した結果をDOSが表示するのに追いつきません。
このような場合は表示を省いてもいいのでしょうか？
また、計算を始めてから結果を出すまでの時間はどうやればよいのでしょうか？
よろしくお願いします。
0757デフォルトの名無しさん
NGNGコンソールに出さずにファイルに出せばいい
0758756
NGNGそれでやってみました
時間の問題は他人のソースをパクって解決しました。
で、結果ですが10億までの素数ならcele700で18秒でした
もっとプログラムの勉強をすれば短縮できそうです。
0759デフォルトの名無しさん
NGNG0760デフォルトの名無しさん
NGNG0761デフォルトの名無しさん
NGNGまさかと思うがラビンテストでやってないよな？
0762756
NGNGただ、ファイルには出力せず、DOSに一部を表示してるだけですが。
もちろん表示してるのは少なくてもしっかり全部計算してます。
また、この定理をコンピューターで使用すると
今までのように素数の桁が大きければ大きいほど加速度的に計算時間が伸びるようなことはなく、
少ない桁のときより少し大きいだけで済むと思われます。
100億とかも調べたいのですが、unsigned long intでも40億程度までしか調べられないんですね・・・。
0763デフォルトの名無しさん
NGNGなんだよ。神が降臨したかと思ったじゃねーか。
0764デフォルトの名無しさん
NGNG割と最近発見された，多項式時間で素数／合成数を判定するアルゴリズムは
係数部分が馬鹿でかいと聞いたがな…
0766756
NGNGｽﾏｿ・・・ 表示するだけとしてはまだまだ遅いんですか？
>>764
自分はそれほど詳しくないしC言語も初心者レベルなんですけど
素数列挙って面白いですね。
AKSアルゴリズム、いつかは自分で理解できるぐらいになりたいです。
0767デフォルトの名無しさん
NGNGん・・・俺が無知なのか？
0768デフォルトの名無しさん
NGNGhttp://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
上には上ｇ（ｒｙ
0769デフォルトの名無しさん
NGNG上の１８秒はCeleron700なので，こっちのが速そうだ
0770デフォルトの名無しさん
NGNGつーか、>>764はさっさとその定理を証明して発表汁。
そうすればもしかしたら素数アルゴリズムブームが起きるかも試練
0771デフォルトの名無しさん
NGNG0772デフォルトの名無しさん
NGNG0773デフォルトの名無しさん
NGNGp=2*3*5*7*11*13*17*19・・・ +1
素数を順番にかけていって最後に1を足せば必ずpは素数ってのを利用して
世界一大きな素数を発見ってできるかね？
これだと結構大きな素数発見できるはずだけど
素数をあらかじめ順番に大量に並べておかないといけないから前処理が大変。
目指せ100万桁ってのは無理かな、無理だね。
0774デフォルトの名無しさん
NGNG>素数を順番にかけていって最後に1を足せば必ずpは素数
電波は混乱のもとになるので帰ってくれ
2*3*5*7*11*13*17*19+1 = 9699691 = 347*27953
何の確証もない仮説を書き込む前に一つくらい試してみろよと言いたい
0775デフォルトの名無しさん
NGNG━━━━━━(ﾟ∀ﾟ)━━━━━━・・・（´･ω･｀）
0776デフォルトの名無しさん
NGNGなるほど初めて気づいた
確かによく考えると
「素数が無限に存在する」ことを証明するこの論法は
素数が有限という「誤った仮定」を利用して
全ての素数（実際は無限に存在するが）を掛けて 1 足すと素数…
とやっているわけだから
無限に存在する素数のうちの有限個を掛けて 1 足す
で成り立つかどうかは分からないんだよな
実際 >>774 が反例を示してくれているし
0777デフォルトの名無しさん
NGNG手計算ではしんどいからやらないが、
2*3*...*p+1
と 2..p の全ての素数を掛けて 1 足した数が合成数となる最小の素数 p は何？
19 より小さい p はある？
0778デフォルトの名無しさん
NGNG0779777
NGNG2 * 3 * 5 * 7 * 11 * 13 + 1 = 59 * 509
13 か…人に説明するネタに使えそう
0780デフォルトの名無しさん
NGNG桁数が上がっても加速度的に計算量が増えないって言うし。
本当なの？
0781デフォルトの名無しさん
NGNG0782デフォルトの名無しさん
NGNG0783Fromごみ箱
NGNGprint "$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;
}
0784デフォルトの名無しさん
NGNGCygwin で実行すると 256 の壁に当たったようで
258 番目の素数として 1622 とか出力してるな
0785デフォルトの名無しさん
NGNGsieve (p:xs) = p : sieve[ n | n <- xs, n `mod` p /= 0]
0786Fromごみ箱
NGNGActivePerlでも1600超えると落ちました
正規表現が大きくなりすぎるのかも
正規表現雑技のページを見て割り算とか篩とか
使わずにやってみたくなったんだけど
シンプルじゃないうえに欠陥品でちょっとガッカリ
0787ついに完成（？）世界最速
NGNGできればそのソースも見たいです。
私が1ヶ月前にこのスレを発見していろんな意見を参考にして作ったのとどっちが早いか勝負してみたいです。
ファイル出力はしなくてもOK、時間表示が出ていればOK
0788デフォルトの名無しさん
NGNGhttp://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
0789デフォルトの名無しさん
NGNG0790デフォルトの名無しさん
NGNG数えるだけじゃダメだろ
0791デフォルトの名無しさん
NGNGそっか、数えるだけじゃダメか。
数えるのも一個一個値出すのも一緒じゃんって思ったけど、
PrimeCountH はエラトステネスじゃないから違うのかな。
数える速さはだんとつで速いと思う。
0792デフォルトの名無しさん
NGNGエラトステネス使ってるだろ。
0793デフォルトの名無しさん
NGNGそれはルートNまでの素数を計算してるだけでは?
0794デフォルトの名無しさん
NGNGそうだけど、それが何か？
0795デフォルトの名無しさん
NGNGだから核となるアルゴリズムはエラトステネスじゃないってことだよ。
あたまだいじょうぶ？
0796デフォルトの名無しさん
NGNGﾊｧ?
素数 "列挙" できるのはそこまでだろ？
スレタイちゃんと読んで出直せ。
0797デフォルトの名無しさん
NGNGだから >>791 の発言につながるわけですが...
0798デフォルトの名無しさん
NGNG見事すぎる。
0799ついに完成（？）世界最速
NGNG出直してきます。
0800デフォルトの名無しさん
NGNGクリエイティブにいこうぜ！！
0801デフォルトの名無しさん
NGNGそもそも素数列挙ってアルゴリズムはエラトステネス一択だし、
素数判定や素因数分解みたいな高尚なテーマに比べるとずーっと奥が浅い。
素数カウントはそれなりに難しいのかもしれない(おれは分からない)。
pi(x) project ていうのあるしね。
0802デフォルトの名無しさん
NGNG素数列挙がさらに高速化するという可能性は無いのか
0803デフォルトの名無しさん
NGNG0804デフォルトの名無しさん
NGNG0805デフォルトの名無しさん
NGNG0806デフォルトの名無しさん
NGNGガウスが15歳の時に思いついたけどガウスにとっては初等的過ぎて証明しなかったやつ
その後誰かが手柄横取りした
0807デフォルトの名無しさん
NGNG0808デフォルトの名無しさん
NGNG0809デフォルトの名無しさん
NGNG0810デフォルトの名無しさん
NGNG0812デフォルトの名無しさん
NGNG多分このスレでも既出だろうし、なにより余白が少ないので
保守だけさせてもらいます。
0813デフォルトの名無しさん
NGNG期待はしてないよ。
既出「だろう」し、ということは「読んでません」と言ってるようなもの。
他人の意見に興味を示さない人に大したことができるとは思わない。
0814デフォルトの名無しさん
NGNG812は、フェルマーのパロディだろ。
0815デフォルトの名無しさん
NGNGおもしろいページを発見しました。PrimeCountHなんかもこの計算方法を使ってるんでしょうね。
http://mathworld.wolfram.com/PrimeCountingFunction.html
0816デフォルトの名無しさん
NGNG2ちゃんねるでやるにはもったいない。
0817デフォルトの名無しさん
NGNG0818デフォルトの名無しさん
NGNGドトール
0819デフォルトの名無しさん
NGNG問題概要：n個の数列をできる限り低速にソートするアルゴリズムを設計実装せよ。
インチキな実装はしてはならない。
そして、そのアルゴリズムの計算量はいくつか？
問題の意図はおそらくO(n^2)よりも遅いソートアルゴリズムを見つけよだと思うのですが…
お知恵を貸してもらえませんか？
お願いします。
0820819
NGNGスレ違いでした。
無視してください。
0821デフォルトの名無しさん
NGNG0822デフォルトの名無しさん
NGNG0823デフォルトの名無しさん
NGNG素数さんと結婚するにはどうしたらいいですか？
0824デフォルトの名無しさん
NGNG子供を産んで、「素数」と名づけるほうが現実的。
0825823
NGNGずっと放置かって
わびしさを感じようと思ってたんだけどな
0826デフォルトの名無しさん
NGNG0828デフォルトの名無しさん
NGNGバカなの？
0829デフォルトの名無しさん
NGNG>>823は確かにageたんだけどさ
>>825はageてないだろ
なのに半日もたたないうちに
>>826のレスがあったから
>>826は定期的にチェックしてるのかよ！！！
っていうレスを>>827でしたわけ
0830デフォルトの名無しさん
NGNG2chブラウザのスレ一覧を最終取得日時か最終書き込み日時でソートしてれば
最近レスしたスレにレスがあればすぐ見ることができるでしょ？
本人じゃないから分からんが別に定期的にチェックしてたのとは違うと思うよ。
0831デフォルトの名無しさん
NGNGこのスレ見てる椰子は
手を上げて
ﾉｼ
0832デフォルトの名無しさん
NGNG0833デフォルトの名無しさん
NGNG0834名無しさん＠Emacs
NGNG0835デフォルトの名無しさん
NGNG0836デフォルトの名無しさん
NGNG0837デフォルトの名無しさん
NGNG68228966604347
0838デフォルトの名無しさん
NGNG9333113 7310419
0839デフォルトの名無しさん
NGNG( ´･∀･`)へｰ
28347681350622442076102437227047036279370375374966
02761076051676968780023033056412274753966959194281
23826876790980636135577027355018080405658377196148
25204708757084342552431413687656764459968946860901
これはどうだ
200桁の合成数です
一行50桁となっております。
0840デフォルトの名無しさん
NGNG7 7 10993 271553 18876064647159886325909391381305666761
2 2 3 1433 18205739579 76108183479522373499388340361881397
246512013571 1157771962604483 88312171996847023952957
それ以上は聞かないで...
0841デフォルトの名無しさん
NGNG0842デフォルトの名無しさん
NGNG0843デフォルトの名無しさん
NGNGどなたかRSA暗号で平文を暗号化して
公開鍵を公開してこの暗号を解いてみろとやってみてくださいな
0844デフォルトの名無しさん
NGNG完全にスレ違い
専用スレでも立てれば？
ただし他の(暗号解読の話題に一番適した)板で
0845デフォルトの名無しさん
NGNG昔作ったやつを改造してみますた。
計算量増えてるけどメモリ効率は良くなってるので、一兆くらいまで計算すると前のより早くなるはず。
10兆とか100兆までの素数すべてを記録しておくことなどできっこない。
かといってメモリ回すだけじゃ意味ないから素数の個数を出力するようにしたんだけど、
数えるだけならもっと速いアルゴリズムがある。
エラトステネスのふるいに価値があるとしたら、ある範囲(結構広め)の素数を探すとか特殊な素数(双子素数とか)を探すとか
になってくると思う。
0846デフォルトの名無しさん
NGNGどこのへんの人だい？
すっかりさびれちまっててすまねぇなぁ
0847デフォルトの名無しさん
NGNG東京電力の検査が来ました (⊃д`)
>>846
621とか396とからへんの人です。あんまりネタないですからね。
昔、N以下の素数をあらかじめ省いて計算するプログラムを書こうと思って、
プログラムを書くプログラムを作って巨大な switch文を生成したことがあります。
すごくコンパイル時間がかかって、バイナリがでかくなって、ちょっとだけ速くなった
とかいう感じでした。
今なら C++で書けばすっきりしそうな気がします(相当マニアックなことしないといけませんが)。
すごくやりがいはありそうなんですが、なかなか暇がないです...
0848デフォルトの名無しさん
NGNGC++使えば確かにすっきりはすると思うけど、
それに伴い速度が、落ちると思うよ…
0849デフォルトの名無しさん
NGNGいくつかの素数の倍数を省いたエラトステネスをを素直に実装すると割り算が必要になってきます。
でもそれは、あらかじめ差分を計算しておくというテクニック(>>331)て回避できます。
素数候補の数も変わってくるので場合分けの数も変わってきます。
こういったメタプログラミングをするのに C++の templateが有効だろうと思ったんです。
でも結構大変で本当に実現できるかどうか分かりません。
あと、思ったより templateの展開が遅いです。11まで省くのは無理かもしれません。
コンパイル時にエラトステネスで素数計算させてみると、100までで7秒くらいなのに200までだと1分以上
かかったりします。
正直 templateのことはまだよくわからないです。
0850デフォルトの名無しさん
NGNGなるほどね
でも、実行時の速度を考えるならテンプレートを作るよりも
Cのソース(の一部)を吐き出すプログラムを作った方が速くなりそうな気がする
テンプレートって色々出来るけど、実行時の処理が重くなる時が多いので…
まぁ、使い方にもよるし、上手く使えれば、そんな事ないかも知れないけど…
0851デフォルトの名無しさん
NGNGその通りですね。
ソースをべたべた張りつけるような用途にTemplateは向いてないみたいです。
inline展開を信用すれば同じことができるんですけど。
とりあえず文字列レベルのマクロで十分なのでm4というのを使ってます。
クォートだらけでわけわからないですけど、まあ意図通りに展開されるのでいいかなあと。
肝心のプログラムはなかなか意図通りに動かないです。
コンパイルに10分以上かかってめんどくさいし。ほんとに速くなるのかな?
0852851
NGNGソースコードは3M弱、実行コードは800Kくらいで、計算結果も正しいものに
なったのですが速度は遅くなりました。やっぱり5の倍数までがちょうどいいみたいです。
自分のより速いのも見つからない上に、たいしたテクニックを使ってないというのもあり
またエラトステネスの意義自体微妙なのでとりあえず終わりにします。
>>694 の Pnをを求めるっていうのも適当に当たりつけてカウントしてからふるった方が
速いんじゃないかって気がします。適当ですが。
0853デフォルトの名無しさん
NGNG0854デフォルトの名無しさん
NGNG0855デフォルトの名無しさん
NGNG0856デフォルトの名無しさん
NGNG0857デフォルトの名無しさん
NGNG0858デフォルトの名無しさん
NGNG1億までの列挙に 9 sec
10億までの列挙に 102 sec
列挙先はファイル
10億で18秒か…、先はなげー
0859デフォルトの名無しさん
NGNGそんな奥の深いアルゴリズムではないのでやれることは限られてます。
1. ふるいをビットで保持
2. 小さな素数をあらかじめ省いておく(おそらく 2,3,5までが最良)
3. 2.によって生じるビットの位置を求める計算を割り算ではなく場合分けで行う
4. ふるいを分割する
僕の知ってる限りではこのくらいです。
あと、
5. 小さな素数(7,11,13,17)の積の大きさのふるいをあらかじめ作っておいて、
それをコピーすることで、それらの素数でふるうための計算を省く
というのもあります。泥くさいですが、意外と効果があります。
1,2,3については >>428にまとまってます。あとはふるいの分割ですが、これによって
3がちょっとだけ複雑になります。
ビットカウントにHacker's Delight方式を使うなど細かいことはありますが
おおむねのアルゴリズムはこんなもんです。
0860デフォルトの名無しさん
NGNGもっとオーダーの良いアルゴリズムがあるようです。
http://cr.yp.to/ntheory.html#primesieves
計算量のオーダーは O(N/loglogN)らしいです。
0861デフォルトの名無しさん
NGNG素数候補に対して2000以下の素数で割ると
前処理の効率が一番いいんだけどな。
0862デフォルトの名無しさん
NGNGCPU 2.0GHz
MEM 1GB
のPCを1000台使って並列処理させて
ビット数が等しい素数p,qの積n(256bit)を
素因数分解しようとしたらどれくらいの時間が掛かりますか？
0863デフォルトの名無しさん
NGNG1億までの列挙に 5.313 sec
10億までの列挙に 56.703 sec
>>859, 860, 861
ありがと （まだコードに落とせてないのもあるけど）
0864デフォルトの名無しさん
NGNGp,qの性質によるだろ。例えば、p.qが双子素数なら、一瞬で終わる罠。
0865デフォルトの名無しさん
NGNG( ´･∀･`)へｰﾍｰ(´ν_.｀ )ｿｳﾅﾝﾀﾞ
0866デフォルトの名無しさん
NGNG10億 28.609sec
ファイルへの出力方法かえたら半分くらいの時間になった
0867デフォルトの名無しさん
NGNG0868デフォルトの名無しさん
NGNG気分転換に860のアルゴリズムで作ってみた
結果は1億桁で 5.186sec
現状、エラトステネスより遅いけど、
いいかげんに作ったプログラムなので仕方ない
明日はもうちょっと作りこんでみる
0869デフォルトの名無しさん
NGNG0870デフォルトの名無しさん
NGNGさてはRSALabの因数分解問題を解いて賞金をゲットしようという魂胆だな
0871デフォルトの名無しさん
NGNG違うよん
0872デフォルトの名無しさん
NGNG新しいコードに列挙漏れが発覚
実装ミス
0873デフォルトの名無しさん
NGNG30*2^32（1280億）まで拡張可能なコードを書いたが、
1億までのビット計算に4.3s、ファイル出力にさらに7.5s
10億までだと、ビット計算に56.1s、ファイル出力にさらに72.6s
これだと、100億までやると、
メモリ512MB、出力ファイルサイズ5GB、総時間40分くらいかかりそうだ。
0874デフォルトの名無しさん
NGNG双曲線の漸近線がよく分からん
アルゴリズムの意図しているものが
本当に漸近線なのかもよく分からん
>>873さんの書き込みで気づいた
２，３，５の倍数を除くってのは
はじめからそれ用のバッファを持たないってことなのね…
すげー勘違いしてた 初期化のときにそいつらだけ０で消すってことなんだと思ってた…
確かにこうしたほうが効率よさそう
一応、僕がエラトステネスやってて思ったことを。
・素数は 6*i+1 6*i+5 にしかないのでそこ以外見ない （>>311)
・なんでか知らんけどｘ／32という計算のほうがx>>5よりも速い（僕の環境では）
・出力はバイナリ出力でwrite関数とか使うと速い（列挙とはちょっと意味が違うけど）
0875デフォルトの名無しさん
NGNGようやく言える。日記はチラシの裏にでも書いてろ。
0876デフォルトの名無しさん
NGNGファイル出力遅すぎじゃないか？
0877873
NGNG{
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);
}
}
現在のファイル出力部分のコードです。
0878デフォルトの名無しさん
NGNG0879デフォルトの名無しさん
NGNG１億 1.859sec
１０億 23.5sec
いまいち自分の実力が分からんから
前にやってた人と環境をあわせようと思って
cygwin g++ -O3でコンパイルしたら
１億 1.281sec
１０億 17.859sec
（ただしファイル出力はバイナリ）
VCで最適化かけたほうが速いもんだと思ってたんだけど…そういうわけじゃないのね
0880デフォルトの名無しさん
NGNGそんな書き込みでスレを荒らさないでくれ。ここは日記帳じゃないんだ。
0881マイク ◆yrBrqfF1Ew
NGNG0882879
NGNGほかの人もやり始めてくれたんじゃないの？
わかんないけどさ。
ボーっと見てれば
レベルの高い人が見所のあるプログラムを書いてくれるとでも思っているの？
お前ら、すごい人のおこぼれ欲しがってるだけじゃん。
惰性で生きてる人間がモラルなんか持ち出すな。
しょうもない
0883デフォルトの名無しさん
NGNG君は最近やり始めて新鮮なのかもしれないが、このスレにとってはなんの価値もない。
本来なら「過去ログ嫁ｳﾞｫｹ」と一蹴されるはずの内容なんだよ。
荒らし以外のなにものでもないよ。882の書き込みにはある種、感動したけどね。
0884デフォルトの名無しさん
NGNG・30*Loopは変数で保持
0885マイク ◆yrBrqfF1Ew
NGNG0886デフォルトの名無しさん
NGNGでないと比較のしようがないと思うのは私だけ？
OS,コンパイラ,コンパイルオプションまで有ればなお良しということで
0887デフォルトの名無しさん
NGNGこのレビューは参考になりましたか？
◎はい ○いいえ
0888デフォルトの名無しさん
NGNG1億まで 6.2秒（テキスト形式でファイルに出力）
2と3の倍数を除いてる。6秒切れない…
0889デフォルトの名無しさん
NGNG明日もよろしくね
0890デフォルトの名無しさん
NGNGテキストで出力すると1億まで 8.843秒（前のはバイナリで出してた）
あぁ、レベル低いって言われてもしゃあないなぁ…
0891デフォルトの名無しさん
NGNG0892デフォルトの名無しさん
NGNG0893r
NGNGhttp://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の足下にも及ばんな...
0894r
NGNG>>879 一億で1.8秒？！！！！
しかも >>880 速度的に陳腐なの？
...すまん...出直してくる...
つか、どんなアルゴリズムだ...
...λ.......
0895r
NGNG% 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
の、糞な部分を指摘キボン....
0896デフォルトの名無しさん
NGNG多分ストリームを使わずprintfにするだけで
かなり縮むと思うぞ。
0897r
NGNGそれがですな...
std::coutを使用せずに、
カウンタのインクリメントに置き換えてみたんですわ。
そしたら、速度が3倍になりました。
３倍。
たかだか３倍。
18秒なんて、夢のまた夢
0898デフォルトの名無しさん
NGNG0899デフォルトの名無しさん
NGNG0900デフォルトの名無しさん
NGNG0901デフォルトの名無しさん
NGNG0902デフォルトの名無しさん
NGNG0903デフォルトの名無しさん
NGNG＞ 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 はいらない。
0904r
NGNG指摘ありがとう。....そうだな。
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秒には、全くかなわないけど。
0905r
NGNGhttp://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秒？ハハッ！
0906デフォルトの名無しさん
NGNGコードや環境の違いがあるから一概には言えないかもしれないけど、
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をチェック、出力
}
0907デフォルトの名無しさん
NGNG0908デフォルトの名無しさん
NGNG0909デフォルトの名無しさん
NGNGその必要はない。
ごく簡単なアルゴリズム、例えばエラトステネスのふるい法を考えても、
一つ一つの数が素数かどうか判定していないでしょ。
0910デフォルトの名無しさん
NGNG0911デフォルトの名無しさん
NGNGNまでの素数列挙とN^2くらいの大きさの数の素因数分解だと後者の方が簡単だと思う。
少なくとも素数列挙できるレベルのNに関しては。
0912r
NGNG0913デフォルトの名無しさん
NGNG0914デフォルトの名無しさん
NGNG0915デフォルトの名無しさん
NGNG0916デフォルトの名無しさん
NGNG0917デフォルトの名無しさん
NGNG0918マイク ◆yrBrqfF1Ew
NGNG0919r
NGNGしばらく仕事でJavaばっかりだったからうっかりしてたのさ。
その点は修正済み。
これを観てアプリケーション終了時に
deleteすべきかどうかについて興味を持った人は、
よそで議論を。
0920r
NGNGhttp://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
0921r
NGNG1. 篩処理と表示処理を分離した
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を明確に分離した。
0922r
NGNGえっと、整数をを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マクロを、呼ばなくていいようにしたい。
0923r
NGNGp(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 );
}
0924デフォルトの名無しさん
NGNG読んだ上で低レベルな話してるの？
発言するより、過去ログ読んだり人のコード見たりしたほうがいいよ。
0925デフォルトの名無しさん
NGNG6n-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個おきにふるう。
これより速いやつあるぅ。
0926デフォルトの名無しさん
NGNG0927デフォルトの名無しさん
NGNG0928r
NGNG見たけど、よくわかんねーんだよ
>>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 のあげてるのと同じになった。
俺、理解していないのに。なんか不思議。
0929r
NGNGhttp://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秒。
目標あと５倍。
0930r
NGNGhttp://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
0931デフォルトの名無しさん
NGNGな！930
0933デフォルトの名無しさん
NGNG1億まで（ファイル出力なし） Pen4 2.4GHz WinXP
>>930（+puts部分コメントアウト）
…7.06秒
漏れのソース
…6.42秒
# OperaとかUDとか起動しまくり状態。
0934デフォルトの名無しさん
NGNG0935デフォルトの名無しさん
NGNG>>930で９秒切れるんなら>>929でも切れるんじゃないか？
0936デフォルトの名無しさん
NGNG0937デフォルトの名無しさん
NGNG#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));
}
0938デフォルトの名無しさん
NGNG{
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;
}
0939デフォルトの名無しさん
NGNGif(argc != 2) return 1;
PrintPrime(atoi(argv[1]));
return 0;
}
428を改造したコードだよ。君のと比べてみ。
君みたいな厨が現われないように859を書いたんだよ。
今となってはこのスレ、落とすのも埋めるのも変わらないかもね。
0940939
NGNGwhileの条件の中は m < sqrt(MAX3/3) で、抜けたあとに
for(; m < MAX3; m++)
if(!TestBits(tbl, m))
PutsInt(m);
て感じで。
mallocの中はMAX3/7くらいで。
0942デフォルトの名無しさん
NGNG0943939
NGNG君は頭なでなでして飴玉あげたいのかい？ 俺にそんな母性本能はないよ。
そうなんないように早めに「最低428」ってハードルを作っといたんだよ。
そしたら平気でそのハードルくぐってきやがった(笑い)。
まあ、こういうのも含めて2ちゃんねるなわけだが。
もういいよ、止めないから埋めてくれ。
0944デフォルトの名無しさん
NGNG0945r
NGNG悪意の無い馬鹿が日記を書き始めたらどうしたらいいって？
放置すりゃいいんじゃね？
２年後に来る「悪意の無い馬鹿」を、止めたいんであれば、
そいつはその当時の熱気を知らないんだから、
「完全なコード」を乗せりゃいいんじゃね？
「そのコードに、自分が負けてるかどうかを簡単に検証できる」
用な環境を提示してやればいいんでは？
っていうか、428のコードは、何をどうするコードであって、
どうすれば「素数列挙」のコードになるの？
２年後にスレを観始めた人が、
そんな、細かいとこまでちゃんと、不完全な物も含めた全コードを、
main関数とかをちゃんとくっつけて、コンパイルして、検証すると思ってたの？
400MHzのプロセッサで50秒かかるコードを。
なんで、428のコードがあれば「悪意の無い馬鹿が日記を書き始める事は無い」
っておもったの？
>>940 にあるような、コードの訂正を、読んでる側の、「悪意の無い馬鹿」がやると思ってんの？
なんでさ、「完全なコード」を掲載しないの？
っていうか「428」のコードに、改造が必要だったのはなんで？
さらに、一億列挙するのに1.8秒のコードがあるのに
1億列挙するのに7秒かかるコードを「最低線」に選んだ理由はなに？
まあ、俺は939のコードに１億までの列挙で1200msecほど負けたので
もそっと精進しますが。
0946デフォルトの名無しさん
NGNG考え方はいろいろあるだろうけど、
やる気のある人間がやる気のない人間のスペースを奪うというのは
２ｃｈ的というより一般的な現象だね
君が向上しようとしていないから、どうすればいいかも分からないんだろうし、
泣いて哀れみ誘うしか止める手段がないんだろうね
0947デフォルトの名無しさん
NGNG0948デフォルトの名無しさん
NGNG単なるマシンパワーなんじゃないの？
0949デフォルトの名無しさん
NGNGconst 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;
}
0950デフォルトの名無しさん
NGNG改行減らすために見にくくなってしまった。
>>946
過去のコードを読まないなんてすごいやる気だね。
俺やる気ないからそこまで適当に発言できないわ。
そんな漏れのコードはこれ
http://primes.dnip.net/primes.tar.gz
>>859 にある5番目のテクニックを使うともっと早く
なるんだけど、あんまり綺麗じゃないから実装前のやつ。
しつこく保守してるヤシがいるなあと思ってたのに...
0951デフォルトの名無しさん
NGNG「～と思ってました」
「自分が望んだのはこんなんじゃありません」
「私は暗にこういうことを伝えたかったんです」
「好きにすればいいです」
なんもせずにそういう言葉を平気で吐ける人間と
実際にがんばる人間だったらがんばる人間を応援したくなるよ。
0952デフォルトの名無しさん
NGNG風邪引いて仕事してて
「あー私風邪でも仕事がんばってるなー」
なんて寝言ほざいてる馬鹿と一緒じゃん
迷惑なんだよ
と何度いいそうになったことか
自分中心で考えてて
周りのことを考えることができないんだろうなと思った。
0953デフォルトの名無しさん
NGNG風邪で仕事来ないでください。伝染ります。
0954r
NGNG「見つけた素数の倍数を、マークする(ふるう？)処理」って言うのは
√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) にあるだろう。
これが漏れの中で飲み込めたら、実装しようと思う。
0955デフォルトの名無しさん
NGNG煮詰まって発言が少なくなったやつは「やる気ない人」、「なんもやらなかった人間」。
やる気ないスレにやる気ある人が書き込んでんだから足引っぱるんじゃねえ。
過去ログ読めないやつのための859だった訳だがそういう問題じゃなかったと。
0956r
NGNG漏れの環境で
% 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秒？...漏れが学ぶべきポイントは多そうだ
0957r
NGNG% 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
0958デフォルトの名無しさん
05/01/18 19:17:04radeon9000proで見れんかった。
グラボはみんな何で見てる？
demo起動->ゲフォ必要->電源落としてカード取り替え＆ドライバ再ｲﾝｽｺ->( ﾟДﾟ)ｳﾏｰ
このくらいの気合があれば良いんだろうけど・・・・
0959デフォルトの名無しさん
05/01/19 09:04:290960デフォルトの名無しさん
05/01/28 08:56:090961デフォルトの名無しさん
05/01/30 18:02:350962r
05/02/05 10:57:22http://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のは相当単純な反復に落としてあるし。
0963デフォルトの名無しさん
05/03/02 18:14:540964デフォルトの名無しさん
2005/03/22(火) 19:27:31http://www5e.biglobe.ne.jp/~liquor/prime/
0965デフォルトの名無しさん
2005/03/28(月) 22:23:350966デフォルトの名無しさん
2005/03/28(月) 23:02:22古すぎて動かないやつもいるのかもね
作者が古いのか、OSが新しすぎるのかｗ
0967デフォルトの名無しさん
皇紀2665/04/01(金) 08:36:100968デフォルトの名無しさん
2005/05/09(月) 09:15:300969デフォルトの名無しさん
2005/05/09(月) 20:52:190970デフォルトの名無しさん
2005/05/13(金) 20:17:49やってみれ
0971デフォルトの名無しさん
2005/05/29(日) 15:20:17_ ´-─ ￢く ￣ ￣ﾐ- ､
,,,,／ _==-ﾐｧ-─‐-､ ＼''''''''''''ｰ--､,,,,,_
_,,,,-''"／ , ‐''" ＼ ＼､_,,,ｰ''ゞ" `ゞ､
-' " / ／ ／ | ＼ ヽ /"`
_,,-''''''"""''''' / ／ ／ / / || | i ヽ i /
´"''､. i / / / / / / || || |│ |ﾉｽ /
'､ |// / /___, -一ｧ| /! |ﾄ、|│ | | く」／
'､ |,-‐￢ ---┘'７ |! ﾊ! |,､-┼十|!／＼／＼
, -‐ ''" し' '´_ ／,ィ二l |ﾄ、/!ヽﾄ､＼_ヽ!|!l＼:.. ／
,r／ __ ,イ|ﾘ ヾハ! ヽ! ,ィ⌒ヾﾐﾘﾉ／:::... ＼
／ ||ヽ -' ／￣ )｀ __ |ヒﾉ:} '` ,;＼／＼／
,r ' ヾ､ ,-､＿___ , イ￣,r=＝- ==-' ﾚ' /| |
／ ヽ `ーｿ ' | |ﾄ､,ﾍ ′"" "" / / || |
. ／ ＼_ ／ | ﾊ ヽ｀ﾞ'ﾍ ' ' ／ / | | | 1000GET
／ / / | ヽ 川＼ 0 ／/! | | | |
/ / / 八 ＼川| |`ト- .. __ , イ‐ｧﾍ | | || |!
／ / / / ＼ ＼ 「`ー- ､ ／ .〉 ト､| ヽ、
,イ ／-─＝￢ﾆヘ､_ ＼ 厂＼ 厂ヽ /!| | `ｰ＝ﾍ
-‐ ￣ /─ ' ￣ ├- ヽ＼ ＼ﾉ＼ ＼ 人 ﾊ!ヽ || |-┤ ヽ
/ ／!‐-- | |＼ ﾄ､_｀ヽ oヽ ﾄ､! || |‐┤- ヽ
／/ 〉 __ ／ ├‐- || | 川-‐ | | 厂7! ﾊ! ├:┤ ￣ヽ
／ / ｰ ─ ￣ ├‐- ﾘ || ﾊ!ﾍ | | ト┤|/′ ヾ,┤ ﾞi_
‐ ' 〉‐- | / /＼ .|o | /ヽ/（′ ∨ ＼
0972デフォルトの名無しさん
2005/05/29(日) 17:24:58２．３．５だと３０のうち８つ
２，３，５，７だと２１０のうち４８
0973デフォルトの名無しさん
2005/05/29(日) 23:33:090974デフォルトの名無しさん
2005/07/08(金) 22:17:420975デフォルトの名無しさん
2005/07/09(土) 09:03:08成分A,Bを求める、またその正当性も求めるというアルゴリズムは
どのようにかけばいいのでしょうか？
知ってる方いましたらどうかおしえてください。
0976デフォルトの名無しさん
2005/07/09(土) 13:32:000977デフォルトの名無しさん
2005/07/09(土) 16:52:50知らないならほっといてください。
知ってる方いましたら
どうかおしえてください。
0978デフォルトの名無しさん
2005/07/09(土) 18:18:230979デフォルトの名無しさん
2005/07/09(土) 23:51:05は最大公約数を求めるものですよね？
それをどういうふうにつかえばよろしいのでしょうか？
0980デフォルトの名無しさん
2005/07/09(土) 23:59:03ほっといたら迷惑なんだよ、お前は。
ここにいちゃいけない人間なんだってことを理解しろ。
0981デフォルトの名無しさん
2005/07/10(日) 01:23:14いくつものスレに迷惑文ばっか載せて
他人迷惑をかけている。
利用規約に反しているので
運営側に報告
IPアドレスから所在地をつかみ
損害賠償
ｵﾒ
0982デフォルトの名無しさん
2005/07/10(日) 03:32:380983
2005/07/10(日) 14:59:500984デフォルトの名無しさん
2005/07/10(日) 15:51:40むしろ神父さん。
0985デフォルトの名無しさん
2005/07/11(月) 02:01:03あ～
怖くなったのか。
乙
0986デフォルトの名無しさん
2005/07/11(月) 02:14:240987デフォルトの名無しさん
2005/07/11(月) 02:19:18再三の忠告にも関わらず
迷惑行為をしていますので
利用規約違反者として
あなたの通信記録より身元を判明させて頂き、
警察等に連絡させていただきます。
0988
2005/07/11(月) 15:47:440989デフォルトの名無しさん
2005/07/11(月) 16:11:010990デフォルトの名無しさん
2005/07/11(月) 16:12:510991デフォルトの名無しさん
2005/07/11(月) 16:13:010992デフォルトの名無しさん
2005/07/11(月) 16:13:520993デフォルトの名無しさん
2005/07/11(月) 16:14:090994デフォルトの名無しさん
2005/07/11(月) 16:36:180995デフォルトの名無しさん
2005/07/11(月) 16:36:330996デフォルトの名無しさん
2005/07/11(月) 16:36:450997デフォルトの名無しさん
2005/07/11(月) 16:37:000998デフォルトの名無しさん
2005/07/11(月) 16:45:060999デフォルトの名無しさん
2005/07/11(月) 16:45:431000デフォルトの名無しさん
2005/07/11(月) 16:46:08調子に乗りすぎました
1001１００１
Over 1000Threadもう書けないので、新しいスレッドを立ててくださいです。。。
レス数が1000を超えています。これ以上書き込みはできません。