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

このエントリーをはてなブックマークに追加
11
メモリとかも考慮に入れた超高速なアルゴリズムを真剣に考えるスレ

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

まだ使えるから そっちでやってよ
61:02/04/13 09:45
71:02/04/13 09:47
>>5
判定と列挙は微妙に違います。向こうで書くと微妙にスレ違いになりそうだったので。
>>7 まあいいけど、 あっちのスレも半分以上は列挙の話題だよ
>>6
そこのリンク、ものすごく低レベルなんだが、
もしかして10桁とか20桁とかそういうものすごい低レベルな話?

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

リンクを見る限り、1自体がこの話題についてこれる気配がしないんだが
101:02/04/13 10:10
>>9
そのとおりです。凄く低レベルです。
数百万桁クラスの素数を列挙する方法があるんですか?
>>10
作ったこともない奴が作った奴を批判する資格はない。
>>10 そんなもんがあったら驚天動地

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

どうせなら100桁(40バイト)くらいの素数を与えてそこから素数を列挙するとか
>>12
64bit限界はエラトステネスのふるいを使った場合
161:02/04/13 10:40
>>14
100桁の素数辞書のサイズが莫迦にならないと思うんですが…
>>16 だから 指定した100桁程度の素数から  28bit程度のフルイビットマップで表現すればいいでしょ?
>>15 他には巧い方法は無いと思うけど? 何かある?

まさか確率判定法でフルイを粗くさばく?
テーブル引き
32Bitの最大の素数って何?1個か2個素数がほしい。
2^32 - 5
もう1個欲しいなら 2^31 -1 も素数だから
じゃ課題を
n0 := 170141183460469231731687303715884105727

n0 〜 n0+0xffff の範囲の素数を列挙せよ
あれ? もう1はヘタったの?

2^127-1 = 170141183460469231731687303715884105727
>>24 1ではないが 計算が終りません・・・(涙
26デフォルトの名無しさん:02/04/18 20:12
>>1-all
てめえらここにソース出してみろ
CUBEって映画思い出した
>>26
オマエモナーって言ってほしい?
29デフォルトの名無しさん:02/04/19 08:46
age
30デフォルトの名無しさん:02/04/19 20:17
数値じゃなくて速さを極めるのでもいいの?
>>9のレベルが酷く低いとしか思えない…
それが可能なら現在のネットワーク社会が
おそらく崩壊するのだが…
32デフォルトの名無しさん:02/04/20 03:16
速度、演算可能数値、コードの短さとかでも極める事には変わりない。

などと間口を広げてみるテスト。
33:02/04/20 03:20
素数ってな〜に??
34:02/04/20 03:23
今、検索かけて調べたら

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

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

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

こんなことがあったYO
2chのみんなで25万j山分けシマッショイ!
35デフォルトの名無しさん:02/04/20 03:47
>>34
最速の素数判定アルゴリズム
http://pc.2ch.net/test/read.cgi/tech/993457354/

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

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

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

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

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

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

これどうよ?
もっと短くできっか?
41デフォルトの名無しさん:02/04/20 22:14
ageるぞ
>>40
> もっと短くできっか?
速度を気にしないならこんなのが7行スレにあったが。

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

てわけで最短はこれでケテーイ?
44昔それ>>42書いた人:02/04/20 23:55
printf(char*,...);main(){int z,i=1;for(;z=i++;z?0:printf("%d,",i))while(i%z--);}
つーかスレ違い。

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

52ヽ(´ー`)ノ:02/04/22 18:20
プログラム言うより数学だろ
53デフォルトの名無しさん:02/04/22 19:31
>>51
荒らしは氏ね

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

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

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

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

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

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

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

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

でよくね?
実行ファイルのサイズがすごそう
小さい数字まで求めたいとき、プログラムのロード時間の方が大きくなって…
73Delフサギコ ◆zE1iiRdQ :02/05/23 13:08
        ∫        _____________
   ∧,,∧ ∬       /フォルダわけて分割したテキストファイルを
   ミ,,゚Д゚ノ,っ━~  <  読み込んだ方がいいよ。
_と~,,,  ~,,,ノ_. ∀  \_________
    .ミ,,,/~),  .| ┷┳━
 ̄ ̄ ̄ .し'J ̄ ̄|... ┃  どこまでか知らんが
 ̄ ̄ ̄ ̄ ̄ ̄ ̄   .┻  素数列を32bitIntegerMaxまで持ったら256MBとか512MB
               程度のメモリが必要だったんじゃなかったかな。
>73
ということは、100Mオーバーのアプリになるのか イヤン
>>73
 2^32/ln(2^32)  *4 -> 780MByte程
 2^31/ln(2^31) *4 -> 400MByte
76デフォルトの名無しさん:02/05/23 18:43
>>65がいいトコついてるね。
2と3以外の素数はすべて6n±1に現れる。
77デフォルトの名無しさん:02/05/23 22:18
>>68
ここでも素数バトルやってるみたい
ttp://haya.s5.xrea.com/cgi-bin/petit/petit.cgi
>2と3以外の素数はすべて6n±1に現れる。

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

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

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

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

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

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

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

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

さらに捕捉ですが、a^p%p の計算は a, a^2%p, a^4%p, ... を作り
必要なのを掛け合わせます(%p しながら)。特に a や p が大きい
場合はそうしないと手間が極端に増加します。
93デフォルトの名無しさん:02/05/25 20:54
レヴェル高いなー
>>93
や、実はその分野を勉強した人にとっては初歩の初歩なんよ。
専門分野が違う人に「おれって頭良いでしょ」とかますハッタリとしては
効果的なんだけどさ。
初等代数学の本に載っているから教養レベルだったかな
数学科だけかもしれないけど
96デフォルトの名無しさん:02/05/26 13:10
>>94-95
そうなのか…ちょいと鬱だ
漏れはエラトステネスを2飛ばしでやるのが精一杯だYO...
保守
98デフォルトの名無しさん:02/06/11 21:43
ageてみたり
99Lisp 1.5:02/06/12 02:10
ちょと違う傾向で。

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

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

:はconsの生成と分解。引数はパターンマッチング渡しで遅延評価。
一行目は、ZF記法っていう置換公理風のリスト生成。
二行目の[x..]は、[x, x+1, x+2, ...]というリスト生成。
100デフォルトの名無しさん:02/06/12 12:31
>99
速さはいかほどでしょう?
101Lisp 1.5:02/06/12 12:41
>>100
modの回数に関するO(n)は普通のエラトステネスの篩と同じです。
-- なこと、いわんでも分かってるか。(しかし何で素数判定法の話に…)
102デフォルトの名無しさん:02/06/12 15:37
では、新しい問題を提案。

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

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

N番目の素数を求めるには、それ以下の素数を全て列挙する以外方法はないだろう。
まぁ、10の整数乗番目の素数はweb 上にけっこう落ちているから、
それを利用すれば多少は処理を速くできる。
103デフォルトの名無しさん:02/06/12 18:02
>>102

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

とりあえず、ここまで求めた
104デフォルトの名無しさん:02/06/13 03:12
素数表現多項式ってあるの知ってる人紹介キボン
確か2変数の多項式で、整数の値を入れた時、値が正になる限り素数
だったような...
全部求められなくとも、巨大な素数をいち早く見つける方法としては
有効かも.
>>104
prime generate polynomial で検索してみた。
見つかったのは、ものすごい26変数の多項式だけですた。
http://mathworld.wolfram.com/PrimeDiophantineEquations.html
こんな連立方程式とても解けねーっす。
106デフォルトの名無しさん:02/06/21 09:38
age
107デフォルトの名無しさん:02/07/12 23:24
漏れら極悪非道のageブラザーズ!
今日もネタもないのにageてやるからな!
 ̄ ̄∨ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
∧_∧ ∧_∧  age
(・∀・∩)(∩・∀・)  age
(つ 丿 (  ⊂) age
( ヽノ ヽ/ )  age
し(_) (_)J
108デフォルトの名無しさん:02/07/17 08:12
   最速の素数判定アルゴリズム  
http://pc.2ch.net/test/read.cgi/tech/993457354/

このスレ落ちちゃったか・・・・
保守
110デフォルトの名無しさん:02/07/27 15:53
このプログラムは優れているのか? 鑑定求む
ttp://www.klic.org/software/klic/lang/node134.html#SECTION008100000000000000000

111 ◆.RANK1Kg :02/07/29 19:16
現在、>>65 >>76 >>78 の路線でちょっと作ってみてます。

>>110 エラトステネス。
Cの配列の練習問題との違いは、素数であることが確定したら
すぐ出力されること。
>>111
がんがってくれ。健闘を祈る。
113 ◆.RANK1Kg :02/07/30 03:43
うーん、>>65 >>76 >>78の発展を「だから?」の煽りに負けず繰り返させて、
「素数でないものを初めから入力列から省き、効率的にエラトステネスを行う」
ということを実現したのだが……。

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

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

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

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

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

E:\>primes 10000000
Target: 10000000                Time  : 16.593sec
numOfPreSieved: 2562069 numOfFalsePrime: 1897492        Fail Rate: 74.0609%
114 ◆.RANK1Kg :02/07/30 03:51
だんだんFail Rateが上昇してます。
つまり、本当の勝負である億以上の世界では意味が無くなってきているわけで……。
STL Listを使ったオーバーヘッドで、多分普通のエラトステネスに負けるでしょう。

ちなみに上記の時間はメモリ内にListで素数列を展開した時の時間です。
Pen4 1.6GHz / DDR-SDRAM 512 MBytes / Windows 2000 です。
ttp://f1.aaacafe.ne.jp/~zxrg/software/psrch.html
ここ参考になるかな?
116デフォルトの名無しさん:02/08/01 17:13
117デフォルトの名無しさん:02/08/01 19:39
>116
エラトステネスだろう。ビット演算多用してるので早そうだ
ただ make_prime_tab 中の k <= nh / 3 がよくわからん。
118デフォルトの名無しさん:02/08/01 19:46
>117
2と3の倍数をはじいてるからか?
119デフォルトの名無しさん:02/08/02 20:13
>>116のコードが理解できない…
保守
121デフォルトの名無しさん:02/08/10 00:38
age
122多項式時間:02/08/10 11:24
 
123デフォルトの名無しさん:02/08/10 20:39
もはや多項式時間なので、ハードウェアの進歩を待つのが吉というデフレスパイラル
>>117
sqrt()や乗算を使いたくなかったのだろう。
ビットを多用しているのはメモリ節約の為(1/32か)。
普通にエラトステネスの篩を使った場合と比べて速くなるかは微妙だな。
125 ◆.RANK1Kg :02/08/14 01:14
例のインドアルゴリズムがこのスレの存在価値を失わせた
訳ではない、とここにも書いておきます。
(私自身は前回のがそれほど効率的でなかったことに気づき
やる気喪失ですが。やるなら2,3の倍数を飛ばすエラトステネスを
お勧めします)

現状まとめ(違ってたら訂正よろしくお願いします):
判定と列挙は別、それに確率的判定なら今まででも出来たし、
現段階ではまだ決定的判定は多項式時間といえど遅すぎる。
2と3の倍数を飛ばすエラトステネスは結構速くなるね。

ところで◆.RANK1Kg氏、下のコードはどうでしょうか?
http://idm.s9.xrea.com/factorization/impl/eratosthenes/esieve4.c
インドアルゴリズムを改良すれば論文にできるね。
128 ◆.RANK1Kg :02/08/14 16:22
ひぇっ、指名されたw

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

私のは「根本的にオーダが改善する」期待があったので、
実際の時間よりオーダを気にしていた……と言い訳させてください。
(ちょっと考えればそんなことは無いことは分かったのですが、
私の数学力だと実際に作って確かめなければ分からなかった)
129 ◆.RANK1Kg :02/08/14 16:29
素数判定に使われるアルゴリズム(確率的でも決定的でもいいですが)って、
素数表を必要としないのが特徴ですが、
素数列挙の場合は自然数Nが素数か調べるときにN未満までの素数表が使えます。

これって生かせるんでしょうかね……。それが良くわからない。
生かせないとしたら、このスレの存在価値は無しなんですが。
生かせるとしたら、エラトステネスを超えるアルゴリズムはあるんでしょうか。
>>126
URL見るだけでエラトステネスだってわかるけど
131 ◆.RANK1Kg :02/08/14 16:36
>>130
1度作ってみると分かりますよ。
素数表を保持する性質上、メモリの無駄を抑えるところで差がつくんです。
>>40を改造した2,3飛ばし。間違っててもノークレームで頼む。

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

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

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

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

          for(q=1;q<=n;q+=3){
            if(P[q]!=1)
              printf("%u\n",q+q+3);
            if(P[q+1]!=1)
              printf("%u\n",q+q+5);
          }
      free(P);
        }
      }
    }
  }
  return 0;
}
あ、一箇所インデント狂った
134デフォルトの名無しさん:02/08/15 00:57
>>1-133
ほんとオマエらヴァカばっかだな。
オレが最速のソース伝授してやるよ。
今回は1桁のみ出力するソースだけど、
少ない脳みそ使って大きな値にも対応しろ。

#include <stdio.h>

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

  for(ii=0; ii<sizeof(primes)/sizeof(primes[0]); ++ii)
  {
    printf("%d, ", primes[ii]);
  }
}
135逝って良しの1:02/08/15 00:59
素数生成多項式ならずううーーーーと前からあったよ。
>>135 それが何か関係あるの?
#include <stdio.h>

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

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

漏れって>>134より頭いい。
>>134>>137も、>>68で概出なのよ

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


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

せっかくかいたので、ageちゃいます。
141デフォルトの名無しさん:02/08/25 00:25
/*
140です。
なんか、うまく展開できなさっぽいので、分割してみます。
全部くっつけてコンパイルしてみて下さいませ。
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MINIMAM_PRIME 2
#define LINES_MAX 100000

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

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

142デフォルトの名無しさん:02/08/25 00:27
// I'm 140 ....
class PrimeGenerator {
private:
unsigned int lines_size;
PrimeLine* lines[ LINES_MAX ];
unsigned long int lastPrime;

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

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

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

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

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

inline void Calc( int n ) {
while( 0 < n-- )
CalcNextPrime();
}
};
143デフォルトの名無しさん:02/08/25 00:27
// 140です。
// メインです。なくていい?
int main( int argc, char* argv[] ) {
PrimeGenerator primeGenerator;
int times = argc > 1 ? atoi( argv[1] ) : 10;
time_t begin = clock();
primeGenerator.Calc( times );
printf("%dth Prime : %ld by %d[clocks]\n",
times, primeGenerator.Get( times - 1 ), clock() - begin );
return 0;
}
144逝って良しの1:02/08/25 00:29
145デフォルトの名無しさん:02/08/25 00:32
>>144
ワロタ。
146デフォルトの名無しさん:02/08/25 09:58

やったぜ、素数見つけた
素数10000個列挙に20秒、
60000個列挙に12分。
これってどう?全然戦えてない?
>>147 dame
Vectorあたりで何個か落としてみろ
>>147
10000個目、60000個目の素数が何だか知らんが
1000000までの素数を列挙する(ちなみに素数の数は78498個)のに
400MHzのCPUで0.75秒。
Vector内では恐らくこれが最速。
http://www.vector.co.jp/soft/win95/edu/se221945.html
151デフォルトの名無しさん:02/08/29 04:49
急浮上
152 ◆DhJkQxJw :02/08/30 00:40
#!/usr/local/bin/ruby
# >>141
MINIMAM_PRIME = 2
LINES_MAX    = 10000

class PrimeLine
    attr_accessor :result
    attr_accessor :prime
    attr_accessor :current

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

    # return value [ true ] mean [ may PRIME ]
    def check( value )
        @result = value != @current
        if ( ! @result )
            @current += @prime
        end
        return @result
    end
end
153 ◆DhJkQxJw :02/08/30 00:40
# >>142
class PrimeGenerator
private
def initialize
@lines = Array.new( LINES_MAX )

@lines_size = 0
@lastPrime = MINIMAM_PRIME - 1
end

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

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

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

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

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

def enum
result = []
@lines.each do |o|
next if o.nil?
if o.result
result << o.prime
end
end
return result
end
end
154 ◆DhJkQxJw :02/08/30 00:41
# >>142 retry (sorry!!)
class PrimeGenerator
    private
    def initialize
        @lines = Array.new( LINES_MAX )

        @lines_size = 0
        @lastPrime = MINIMAM_PRIME - 1
    end

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

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

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

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

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

    def enum
        result = []
        @lines.each do |o|
            next if o.nil?
            if o.result
                result << o.prime
            end
        end
        return result
    end
end
155 ◆DhJkQxJw :02/08/30 00:42
# >>143
if __FILE__ == $0
primeGenerator = PrimeGenerator.new
times = (ARGV.empty?) ? 10 : ARGV[0].to_i
t_begin = Time.now
primeGenerator.calc( times )
puts primeGenerator.enum.join( " " )
printf("%dth Prime : %d by %d[clocks]\n",
times, primeGenerator.get( times - 1 ), Time.now - t_begin )
end

# ふう。。。Rubyに移植してみたのれす。。
# でも・・・・・遅いっすね★
>>◆DhJkQxJw
俺はRubyのコトはよく分からんのだが過去レスに色々ソースがあるから
見てみ(大概Cだけど)。

がんがれやヽ( ´ー`)丿
157 ◆DhJkQxJw :02/08/30 08:22
・゚・(ノД`)・゚・ウワーン
漏れの活躍してた素数スレが消えちゃったよ〜★

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

↑ここ逝っても何もないしさぁ・・・。
>>157
しばらくすると消えるから必要なレスをコピペして。
http://pc3.2ch.net/test/read.cgi/pc3tr/1030500162/
正直、どこをどう読めば活躍してるのか分からない。
頑張って勉強していたスレ、というなら認めるが。
活躍というなら、>>126を超えてくれ。
160 ◆DhJkQxJw :02/08/30 22:50
>>158
うひひ☆サンクスれす☆

>>159
ごめそね★
「暗躍」って言い換えればいいれすか?
161 ◆DhJkQxJw :02/08/30 22:54
ちなみに、漏れが自力で作った最速コードは
これ↓れした。いかな厨房でも理解できそうれす。

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

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

これでも>>152-155よりは早いのれす。
求めた素数をすべて配列に保持するアルゴリズムを
実装すると、かえって速度が落ちるようなのれす。
うひひ。
>>160
無駄レスするな。暗躍の意味をわかっているのか小一時間。

>>152より上を見るのがかったるくなってしまったが>>150は速いな…
163 ◆DhJkQxJw :02/08/30 23:02
昨晩は>>116のコードをRubyに移植しようと
がんがっていたのれすが、ポインタに対して
ビット演算してたりして、お手上げれした。
これから>>126を移植すべく、アサヒ スーパー
ドライを含んだ頭でせいぜいがんがります。
よろしく☆
こんな奴が俺より年上なのか、情けない。

かすみ遊戯のかすみみたいな口調虫唾が走る。
165 ◆DhJkQxJw :02/08/30 23:08
>>164
うひひ★どうせ漏れはドキュソれすよ★
ドキュソはドキュソらしくしてるのが
一番なのれすよ★
ハァァ・・・
>>165
お前が酒を飲むなんぞ10年早いわ。
だいたい >>126 のruby版は既にあるし。
167 ◆DhJkQxJw :02/08/30 23:36
>>166
20歳だから飲んでもいいんだもん★
つーか「かすみ遊戯」って何?
って思ってぐぐるしたら、エロゲじゃん。
げろげろげろー

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

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

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

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

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

・・・・・・試合放棄してもいいれすか?
>>167 試合放棄?
そうか、ここまでよく頑張ったな。いいよ。
169 ◆DhJkQxJw :02/08/30 23:41
・゚・(ノД`)・゚・ウワーン
いぢめっこがいるよ〜★

                 ┌─┐
                 |も.|
                 |う |
                 │来│
                 │ね│
                 │え .|
                 │よ .|
      バカ    ゴルァ  │ !!.│
                 └─┤    プンプン
    ヽ(`Д´)ノ ヽ(`Д´)ノ  (`Д´)ノ    ( `Д)
    | ̄ ̄ ̄|─| ̄ ̄ ̄|─| ̄ ̄ ̄|─□( ヽ┐U
〜 〜  ̄◎ ̄  . ̄◎ ̄   ̄◎ ̄   ◎−>┘◎
170 ◆MAKNgZ1Q :02/08/30 23:53
はじめまして〜☆
こんばんわ〜☆

さっそくですけど、>>150ってすごいれすね。
10億まで計算しても>>161の10万より早いとは。
Uvaで参戦しようと思ったのれすが、もうだめぽ・・・★
面白くない。
保守
173デフォルトの名無しさん:02/09/03 18:00
>>172
ていうか、sageてない?
>>173
sageのまま保守することがいけないことか?
175デフォルトの名無しさん:02/09/03 22:01
>>174
禿同!!

保守はsageでするべきだと思う。
>>175
そういいながらageて書く君が好きだ

ちょっとでも速いアルゴリズムを書きたいが小手先の技になりそうだな…
>>176
やってみれば。
小手先の技でも塵も積もれば山となる…かも
そうだな
179DQN.cc:02/09/06 01:09
そうれすね
180デフォルトの名無しさん:02/09/06 01:55
俺付属の脳コンを使うと
A>list 素数
1、2、3,5、7、11、13、17、19、23、26、29、31、37とでてくる。
A>
181デフォルトの名無しさん:02/09/06 02:04
>>180
馬鹿31は素数じゃねぇよ
>>181
馬鹿はあんただよ…
おばかさん1は素数じゃねぇよ

と言ってみたかったと無理やり弁護してみるテスト。
8 * 9=31
は  く さい
白菜
めっちゃ素直にふるいを実装。
% time ./era 10000000 78497
prime[78497] is 999983
3.560u 0.390s 0:04.16 94.9% 0+0k 0+0io 0pf+0w
G4450Mhz でこのくらい。
「./era」がバイナリ。
最初の引数が、ふるいの大きさ。
次の引数で、いくつめの素数を表示するかを指定( チェック用 )

アイデアがあるので、これから改造。
>>185 頑張ってくれ。俺はこれといった面白いアイデアが無い。

ところで、999983 は78498番目の素数だと思う。
0からカウントをしているということか?
「いくつめ」という時は普通1からだよ
187DQN.cc:02/09/07 14:36
>>185
改造したらソースきぼ〜ん☆
188デフォルトの名無しさん:02/09/11 22:22
>>188
数はあるけど…
190188:02/09/11 22:33
まぁ、プログラミングの練習の段階ですから
191185:02/09/13 02:36
"直感的な素数の倍数を飛ばす[ふるい]”を実装してみました。
% 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行にもなっちゃった。
あぷろだにうp!
数が大きくなればなるほど素数の出現頻度は低くなるの?
>>191
凄く厨な事聞いてるみたいで恥ずかしいのだが、
>1.940u 0.400s 0:02.55 91.7% 0+0k 0+0io 0pf+0w ( G4 450MHz )
これの読み方がわからぬ(;´Д`)
何が何を表してるのか教えてくだされ。。
195185:02/09/13 08:13
>>193
π(x)〜x/log(x)なんだそうな。
だからちょっとずつ頻度は低くなる。
>>195
ファイルが見つかりません…
199185:02/09/14 00:31
>>198
それです!指摘サンクス!
なんで間違っちゃったんだろう....遅刻までして....
あー。死にたいなぁ。


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

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

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

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

これくらいのプログラムなら main にダラダラ書いてもいいんじゃない?
可読性は下がるけど、速度面では有利だと思う
201185:02/09/14 23:03
>>200
っていうか、漏れアフォなので、
一個のメソッドが30行くらいを越えると、
全然理解できなくなっちゃうのです。
誰かmainにまとめたバージョンうpきぼんぬ
age
>>202
七行スレに依頼しる!
>>204
見づらさが500%増加の見込み
出入りの激しいループの奥深くの関数以外は速度面から見てもベタ書き不要。
コンパイラによってはinline指定子もあるし。

まだレジスタの出入りの心配をした方がましかと・・・・・・。
>>206 正論だな
208デフォルトの名無しさん:02/09/17 00:56
素数なんて列挙してどうするの?
209デフォルトの名無しさん:02/09/17 01:02
>>201
30行?カスだな。
>>208 より速く、より高く、より遠くへ。男のロマソだ。
>>210 同意
シンプルな問題ではあるが、奥が深い
素数自体がおもしろい数だし
>>208
賞金もらえるぞ
そこに素数が(可算個)あるからだ。
hoshu
限界目指してます
ほっしゅ
列挙ってことは、配列かなんかに
素数を全部入れなきゃ駄目?
>>217 標準出力とかに順番にヌケも間違いも無く出せればそれでいいと思うよ。
>>217
速さを目指すなら、バイナリでファイルに出力することを推奨
最後は可読な状態で出力がいいな。
バイナリだと何でもありになりそうだから…
221デフォルトの名無しさん:02/09/30 21:20
>>220
出力0.0001秒、表示200時間とか?
んなのがあるかい
>>220
そうだな。
じゃあテキストで、tab 又は 改行で区切るってことで。

個人的には , で区切るのはやってほしくない。
言語によっては、ファイルを読む処理がめんどくなる
224デフォルトの名無しさん:02/10/01 01:20
素数なんか列挙して何になるの?

全然プログラミングと関係無いねえじゃん。
数学板帰れよアホ。
225デフォルトの名無しさん:02/10/01 01:33
>>224
禿しく慨出。
>>224
数学は列挙したりなどしない。定義さえすれば、そこにあるものだから。
そして利用する場合には、プログラム的なアクセスが必要になる。
板違い。
数学とプログラム、特にアルゴリズムは深い関係があるのを知らないのかい
素数列挙列挙ではあんまり数学的なテクニックが使えないからねえ。
素数列挙って言うと、
1:エラトステネスの篩
2:順番に素数判定
の二つしか知らないのだけど、もっと素敵な列挙法ってないでしょうか?
231デフォルトの名無しさん:02/10/04 22:31
>>230
素数データベースから読み出して表示
(列挙は列挙でしょ♪)
enumerate of prime numbers.
適当な奇数を表示して問いかける。
234デフォルトの名無しさん:02/10/07 23:32
>>233
意味が良くわかんないんだけど。
説明していただけるかしら?
>>234

21 は素数ですか?)(y/n) _n
21 は素数ではありません。
13 は素数ですか?(y/n) _y
13 は素数です。
(以下同じ)
それは、>>230の2に該当ということでいいのか
結局エラトステネスが一番素敵だと思う。
プラス2の倍数を飛ばしてみたり。

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


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

あとは早い言語で、良い実装をする。これに尽きる
あと如何にメモリの使用量を抑えるかですな
241デフォルトの名無しさん:02/10/10 01:10
>>237
無限に存在する素数を相手にする時に限界があるよね。
2の倍数、3の倍数の枝刈りのようなもの。
>>242
俺たちにゃ有限の時間しか残されていないのだから、有限でいいのさ
244デフォルトの名無しさん:02/10/12 07:14
ピタゴラス数を列挙(・∀・)シヨーヨ
a²+b²=c²な数を!
[{3,4},{5}]
bracket brace three comma four brace comma brace five brace bracket
>>244
それセンター試験でやった。懐かすぃ
素数列挙。篩ばかりがもてはやされているが、
敢えて isPrime系を選択してみた。
isPrimeには、平方根を求める操作が必須だ。
「sqrtのアルゴリズムは知らないが、
 そんなに軽くないんじゃないの?」
そんな直感が、僕にこのコードを書かせた。
>>248
どのコードよ?
250248:02/10/13 10:05
書き込もうと思ったが、長過ぎたようだった。
251248:02/10/13 10:10
#ifndef PrimeEnumerator_included
#define PrimeEnumerator_included
#include "RootEnumerator.h"
typedef unsigned int prime_t;
class PrimeEnumerator {
protected:
    prime_t  prime_max, prime_count, current, root, divider, i;
    prime_t* prime_list;
    RootEnumerator rooter;
    inline bool CurrentIsPrime() {
        root = rooter.Next();
        for( i=0; i<prime_count && ( divider=prime_list[i] ) <= root; i++ )
            if( current % divider == 0 )
                return false;
        return true;
    }
public:
    PrimeEnumerator( prime_t new_max );
    ~PrimeEnumerator();
    void Calc(); 
    inline prime_t Get( prime_t i ) {
        return i < prime_count ? prime_list[i] : 0;
    }
    inline prime_t GetCount() {
        return prime_count;
    }
};
#endif
このファイルは、 PrimeEnumerator.h という名前で。
252248:02/10/13 10:11
#include "PrimeEnumerator.h"

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

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

% 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 オプションをつけて、コンパイルした。
255248:02/10/13 10:22
このプログラムの rooter.Next() という記述を、
(int)sqrt( current ) に変更して実行してみると、
10000000までの素数の計算に、 3秒ほどよけいにかかるようになる。
30行ものコードを追加して、3/10000000 秒程度の
高速化しかなされていない。

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

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

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

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

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

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

どっちばれ。
全部を一ファイルにまとめている。

#!/usr/local/bin/ruby

class PrimeEnumerator
protected
def CurrentIsPrime
@root = @rooter.Next
0.upto(@prime_count-1) do |i|
break unless ( (@divider=@prime_list[i]) <= @root )
return false if( (@current % @divider) == 0 )
end
return true
end
>>257はボツ。やり直し。

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

#!/usr/local/bin/ruby

class PrimeEnumerator
protected
    def CurrentIsPrime
        @root = @rooter.Next
        0.upto(@prime_count-1) do |i|
            break unless ( (@divider=@prime_list[i]) <= @root )
            return false if( (@current % @divider) == 0 )
        end
        return true
    end
public
    def initialize( new_max );
        @rooter = RootEnumerator.new
        @prime_count = 0
        @prime_list = Array.new( @prime_max = new_max, 0 )
        @rooter.SetFirst(2)
    end
    def Calc
        2.upto(@prime_max-1) do |current|
            @current = current
            if( self.CurrentIsPrime )
                @prime_list[ @prime_count ] = @current
                @prime_count += 1
            end
        end
    end
    def Get( i )
        return (i < @prime_count) ? @prime_list[i] : 0
    end
    def GetCount
        return @prime_count
    end
end
class RootEnumerator
protected
    def SetLimit
        @limit = ( @root + 1 ) * ( @root + 1 )
    end
public
    def initialize
        @number = @limit = @root = 0
    end
    def SetFirst( i )
        @root = Integer(Math.sqrt( @number = i ))
        self.SetLimit
    end
    def Next()
        if( @limit < (@number+=1) )
            @root+=1
            self.SetLimit
        end
        return @root
    end
end
if __FILE__ == $0
    i = (0 < ARGV.length) ? ARGV[0].to_i : 10000
    primeEnum = PrimeEnumerator.new( i )
    primeEnum.Calc
    count = primeEnum.GetCount
    printf( "%dth prime -> %d\n", count, primeEnum.Get( count-1 ) )
end
262248:02/10/13 11:41
>>256
実行環境を教えて下さいませ。
>>262
Windows 2000 Pro SP3 + Cygwin 1.3.12 + ruby 1.6.7

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

UD, Winny, Mozilla, かちゅ〜しゃ常駐 です。
264デフォルトの名無しさん:02/10/13 11:58
結局エラトステネスしかないってわけか。
ただし、同じ環境でもc++では早かったから
Rubyが遅いだけ、と思いねぇ。

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

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

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

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

$ time ./primer 10000000
664579th prime -> 9999991
real 0m13.577s
user 0m12.156s
sys 0m0.061s
C++を素直にRubyにしたコードよりも、
もっとRubyらしくした方が、高速になりませんか?
267デフォルトの名無しさん:02/10/19 01:52
「数学のたのしみ」という雑誌の28号に素数のおもしろい話がのってたよん
ちと高いが
268デフォルトの名無しさん:02/10/19 11:13
すごいよ

#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;
}
何がじゃ
270デフォルトの名無しさん:02/10/20 13:23
>>268
30点。
正常に素数を列挙することに精いっぱいで
高速化のための工夫がまるでありませんね。
ただ、どんな本やお勉強サイトにも
こんなコードは載ってないでしょうから、
>>268さん自身が自力で書いたコードであることが解ります。
この点は、評価に値します。

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

期待していますよ。
ところで、数学のこと全然知らないDQNなんだけどさぁ、

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

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

最高100までとかの制限はもちろんありだけど
最高どこらへんまで有効な式が見つかってるのかなあ。
>>267
引用してよぅ。すごい興味あります...
>>271
関数の形で素数を表現するだけでしたら、
集合 {y | gcd(1,y)=1, y!=1} に順序を与えればよいってことで。
{y|IsPrime(y)=true}
>>273
うーみゅ。数学に詳しくないからあれなんだけど、
ある程度の数まで有効な素数ジェネレータがないか
ってことなのれす。。。
昔どっかの掲示板で、
「任意の有限の数列を表現する 一般的な方法」
をみた気がする。
277デフォルトの名無しさん:02/10/20 17:20
ハァハァ・・・うーみゅ・・・(;´Д`)
ハァハァ・・・エトラステネス!(・∀・)
>277
不安になってググッちまったよ。
残念ながら、エトラステネスでは一件もヒットしなかった。
>>275

その関数はある・・・からこそ計算機で計算もできる。
有無じゃなくて、計算にかかる時間が問題になってるわけです。
281もまずにパピコ:02/10/20 17:39
>>279
エストラテネスなら2件ヒットしたぞ。
>>280
>>275が欲しがっているのはシーケンシャルな計算なしで、
一発で( O(1)で )素数を求めるための式でしょ。


アルゴリズム的な方法をとるのなら、
int prime( int i ) {
    static const int p[100] = { 2, 3, 5, 7, 11 , ... };
    return p[i];
}
みたいな関数作っておけばいいだけなんだけども。
数学的な数式となると...数学板で聞いた方が早いかな。
283267:02/10/20 18:14
>>272
http://www.nippyo.co.jp/maga_suutano/st28.htm
スマン 立ち読みで済ませてしまった。1600円もするから。
内容は、素数のいろいろな定義の仕方から始まって、
素数の数え上げ、素数の間隔、双子素数など。
ページ数もかなりさいてある。図書館にあればコピーしたいなぁ
>>282
たとえば
 (A) n + 1
ならnが1から2までなら成り立つっしょ?

こんな感じの簡単な数式が欲しいのれすが、
どうもスレ違いな予感。。。
メルセンヌ何とかやらとか…
確かものすごい次数の式になった気が。

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


#「そんなん」で「成男」出たよ。なんじゃこりゃ
>>285
いや、だから100までとか1000までとかの間に
限って成り立つ式なら簡単な数式でも
ありそうなものだと思ったわけでつ。。。
自分で作れば?
100までの素数を解にもつ多項式なら作れるじゃん。
たとえば10までだったら
(x-2)(x-3)(x-5)(x-7)=0
これが>>286がほしい方程式じゃん。
ごめん、関数と方程式間違えた。。。
289287:02/10/21 13:58
でも関数なら
f(x)=ax^3+bx^2+cx+d
と置いて、
f(1)=2,f(2)=3,f(3)=5,f(4)=7
を解けば未知数4個で式も4つだから10以下の素数求められるんじゃん?
同じように力技で100だろうが1000だろうがいけると思う。
素数がわかってなきゃ解けないから意味ないけど。
290287:02/10/21 14:27
っていうかラグランジュ補間とかニュートン補間でいけるか。
何度も書き込みすまそ。
291268:02/10/21 17:39

超すごいよ

#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;
}
成長があまり見られん
293デフォルトの名無しさん:02/10/22 03:00
while(0){
fprintf(stdout,"計算中です!!(止めないで)");
fprintf(stderr,"(次の素数をお願いします…(こそーり))");
scanf(&x);
fprintf("あ?次の素数?%dに決まってんだろボケ",x);
}
294Delフサギコ ◆A6VzDeLphI :02/10/22 09:32
素数列挙してよし。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1035246186
            _____________
   ∧,,∧    /
   ミ,,゚Д゚彡 <  書いてみたです。
   ,;゙   ミ     \ 
 @ミ,,,UUミ       ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
       エストラの2の倍数/3の倍数を使ってみますた。
       そんなに高速化できませぬですた。
>>294
だから、エストラとかかかないでよ!
どれが正解だか解んなくなるしさ!

>>291
40点。
だからさ、countが2になったらループ続ける意味ねーだろ。
 ミ,,゚Д゚ミつ...反応が、、、、ニャイ、、、、だれかコードのあれとか、、、
                     コメントないの?
>>296
1億 or 10億 or 2^31 or 2^32 以下の素数を求めるのにかかかる時間と実行環境オセーテ
>>296
すまん。つーか、コード長過ぎて、見る気がせん。
のんきな人だったら、週末まで待ってくれ。

あと、計算時間と実行環境は知りたいなぁ。
Delphi なんて持ってないし、ってゆか漏れマカーだし。
            _____________
   ∧,,∧    /
   ミ,,゚Д゚彡 <  すごく遅いはずよ。
   ,;゙   ミ     \ 
 @ミ,,,UUミ       ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
ビットごとで素数か否かを判断して
2の倍数と3の倍数を削除してるだけだから。
ドノーマルのフルイです
メモリ使用量は少ないので.
容量が必要でオチるのはないと思うですが

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

・・・いや、激しく外出だとは思われなんですが・・・
300Delフサギコ ◆A6VzDeLphI :02/10/24 00:51
 ∫,,,,,,,,,∧,,∧   300ゲト
⊂,,,,,,,,,つ,,゚Д゚ミつ
        このスレ、、住人少ないの?
6ヶ月でレスが300というのは、少ない方だろう
 ∫,,,,,,,,,∧,,∧   3日経っても
⊂,,,,,,,,,つ,,゚Д゚ミつ Int32.Maxまでの素数は
           求まっていなかった,,,もしかしたら300日くらいかかる?
>>302 ガンガレ
こっちに書きます。
>どうせなら 3*5*7*11*13 のテーブルを用意してリピートして使えば
>17から開始出来ます。

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


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

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

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

var tbl:array of byte;

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

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

function TestIsPrime(n:Cardinal):boolean;
begin
Result:=((n and 1)<>0)and ((tbl[n shr 4] and (1 shl((n and $F) shr 1)))=0);
end;
なお、TestIsPrimeの中で偶数ならfalseを返していますが
速度を考えるならホントはループ中に入れない方がいいです。
偶数でも値が2の時はTrueを返すとかの処理も

ただ、SetBitに比べると頻度はずっと小さいので
Test関数が遅くても それほど遅くはならないですが
             ___________
    ∧,,∧     /
   ミ,,゚Д゚彡 <  さんくすこですー
   ミ つ日   \___________
 .@ミ,,,,,, ,,ミ
>それをMove関数を使ってコピーし、
理論は理解しました。
でも。その初期化処理を具体的に
どう実装するのかがわからんですの。

TBitsとかTBooleanDynaArrayとかTListとかだと
ItemやBitsをMoveで初期化するのって
どうやるのでしょうか。

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

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

と、書いてから305以降をハケンしますた。読んでみます。

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


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

普通に書けば32bitのふるいはメモリが300Mあるマシンなら10分もかからないで完成する筈ですから
2の倍数だけでなく3の倍数を表から除くテクニックを利用する場合、
nの倍数を埋める場合、6で割った余りが 1と5の時だけ埋めれば良いので
n2:=2*n n4:=4*nと用意しておいて、交互に足します


7の倍数を埋める場合 初期値x=7*7=49 6で割った余りは1なので 49を埋めた後次は x:=x+n4 その次はx:=x+n2とループします
忘れていました。
 2,3の倍数を表から除いた場合、
セットすべきビット位置は x div 3 で 求まります。
コードとしてはこんな感じです。 TBits.Bits[] を使って

n:=5;
while n< SQRTMAX do begin
if not Bits[n div 3] then begin
  writeln(n,' ',GetTickCount-t0);
  x:=(n*n) div 3;
  n2:=2*n;
  n1:=(n div 6)*4+3;
  while x<MAX3 do begin Bits[x]:=True;Bits[x+n1]:=True;inc(x,n2);end;
end;
inc(n,2);
if not Bits[n div 3] then begin
  writeln(n,' ',GetTickCount-t0);
  x:=(n*n) div 3;
  n2:=2*n;
  n1:=(n div 6)*8+1;
  while x<MAX3 do begin Bits[x]:=True;Bits[x+n1]:=True;inc(x,n2);end;
  end;
  inc(n,4);
end;
コード中の while x<MAX  の停止条件が甘いので、BitsのSizeは(MAX+SQRTMAX)/3にしておいた方がいいです
>>312
function TPrimeListTBitsTripleOverCompress.AccessInsideIndex(
 OutSideIndex: Integer): Integer;
begin
 Result := ((OutSideIndex div 6)*2)
      +
      ((OutSideIndex mod 6) div 5);
end;
こんな感じだと思ってたのですが、
これって、x div 3 なのでしょうか?

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

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

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

|,,∧  アラヤダ すごいわぁ
|Д゚彡
| U
| ミ   
>>314
除算は整数でも浮動小数点ユニットが使われたりで、並列演算が出来ないから
そういうふうに連続して使わない方がいいよ。 合計3つも連続して使うとストールする。
|,,∧   素数列を文字列でスペース区切りしたらMaxInt32で
|Д゚彡 ファイルにして、1ギガになちゃう勢いなんですが
|⊂ミ  …
| ミ    Webにウプする場所がない…
|''U そもそも、俺の56K回線では…
誰かCに翻訳してくれ…意味がわからん。・゚・(ノД`)・゚・。
>>318 そんなもの計算させる前に見積もりさせないとさあ

フルイの状態が一番効率がいいんだよ。だからフルイのままで持っておいて問合せに対して
出力させたら? でも100MもRAM取ると鯖屋に嫌われるか
とだけ書くと、単なる煽りなので
0〜N を10進で改行付で列挙する場合のおよその必要バイト数
 
N*(log10(N)+2)/loge(N)
l
>>319
どのコードを?
>>322
>>305,308,313
つまり全部…
int TestBits(unsigned char *tbl,unsigned int bit)
{ return tbl[bit>>3] & (1 << (bit &7));
}
void SetBit(unsigned char *tbl,unsigned int bit)
{ tbl[bit>>3] |= (1 << (bit &7));
}
unsigned char * MakePrime32bit( void )
{
const MAX3=0x55555555;
unsigned char * tbl = malloc(0x20010000/3);
unsigned int n=5;
 memset(tbl,0,0x20010000/3);

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

 return tbl;
}
int isPrime( unsigned char *tbl,unsigned n)
{ switch(n%6){
  case 0: return 0;
  case 1: return !TestBits(tbl,n/3);
  case 2: return n=2;
  case 3: return n=3;
  case 4: return 0;
  case 5: return !TestBits(tbl,n/3);
 }
}
ありゃ こうか
int isPrime( unsigned char *tbl,unsigned n)
{ switch(n%6){
  case 1: return !TestBits(tbl,n/3);
  case 2: return n==2;
  case 3: return n==3;
  case 5: return !TestBits(tbl,n/3);
 }
 return 0;
}
327デフォルトの名無しさん:02/10/25 22:45
で,テストプログラム
int main(int argc, char* argv[])
{ unsigned char *tbl= MakePrime32bit( );
 int n=29999900,i;
  while(1){
scanf("%d",&n);
  for(i=0;i<10;i++){
    while(!isPrime(tbl,n))n++;
    printf("%8d\n",n++);
  }
 }
 free(tbl);
return 0;
}
29999903
29999923
29999927
29999941
29999947
29999989
29999999
30000001
30000023
30000037
>>304
どこから来たの?どのような概念?

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

ゴメン、詳細キボン
329デフォルトの名無しさん:02/10/25 23:14
324は >>313をcで書いたものです。

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

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

>>304 の件は >>310 の通り、実施してもビックリする程早くはなりません。
>>324 のようなテクニックの方が確実に早くなると思います
330328:02/10/25 23:24
わざわざ詳細な解説有難うございます。
感謝します。
331デフォルトの名無しさん:02/10/26 18:47
n1:=(n div 6)*4+3 のようなマジックナンバーが疑問なのかな?

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

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

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

これは基本的に身に付けておくべきテクニックの一つです。
更に混乱した
確かに>>.324は速いね。 最速かな?
>>333
そんなに速いの? バイナリupキボン
>>334
GCCでもBCCでもコンパイル出来るだろ
>>334
フサギコのコードより倍のサイズを列挙してるのに、3桁以上速い
具体的にどのくらい早いの?
たぶん2千倍くらいじゃない? 想像だけど
エラトステネス 対 除算なら千倍ちかく差がでるのは分かってたけど
エラトステネス同士でも実装次第で千倍くらい変わるんだ へぇ
 ミ,,゚Д゚彡 
私も自分のコードを1000倍くらい高速化したですよ。

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

Int64最大値までの素数値列を出すのはかなり遠いですね。
>>340
まずInt32MaxIntって書くより 2^31-1 って書いてくれた方が判り易いよ

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

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

やるとすれば、2^64-1で指定された場所から 2^31個のフルイを作る事でしょうね
            _____________
   ∧,,∧    /
   ミ,,゚Д゚彡 <  さらさらっとそういう計算できるのって
   ,;゙   ミ     \ なかなか頭の切れがよいですね。
 @ミ,,,UUミ       ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
2^31-1 = 2147483647
2^63-1 = 9223372036854775807

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

同様に計算すると
9223372036854775807のフルイに必要なのは
384307168.ギガバイトですかね。
オンメモリで用意できるのはずっと先ですか...
>>342
例の定理が正しいとすれば
50年先ですから、生きてる間に見える可能性は高いかな・・・いや、CPU速度が追いつくのはさらに倍か
6ヶ月でレスが300というのは、少ない方だろう
345デフォルトの名無しさん:02/10/28 00:46
だーかーらー。
http://pc3.2ch.net/test/read.cgi/tech/983191866/910-911
が最速なんだってば。
>>345
とりあえず10億まで計算させてみろ! 話はそれからだ
>>345
(0〜2^31) という条件だと、難しいんでは?
348デフォルトの名無しさん:02/10/28 16:26
132番目の素数はもう出たの?
>>348

2^743-1 は素数ではありません
std::pow(2, 743)-1

4.62686e+223

(・∀・)?
46268644699475435470014199270680622913148582491776246164412857235254375716637876222457838321585848270371190628323884999935972095850551557285913445801770125007762163162852820919462003875720454598226040577701224945512200798207
なんで224桁もあやふやにならずに書けんだよ!
と問いたい。おっぱいを突付きながら問い詰めたい。
UBASICを使えば簡単

ところで、132番目の素数って何のこと?
メルセンヌ素数は 40番目くらいを探索中でしょ
>>352
俺にも突っつかせろ
>>353
「132番目の素数さん」は数学板のデフォルトの名無しさん。
132番目の素数が743(名無しさん)であることから。
356デフォルトの名無しさん:02/11/05 02:08
浮上
                _____
      ∧,,∧___   /
    /ミ゚Д゚,,ミ/\<  とりあえずupッときまつた
  /| ̄∪∪ ̄|\/ \_____
    |____|/

http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1035246186&res=10
これ動かしたら、10時間後には
0〜int32最大までの素数列
スペース区切りで数値の書いたテキストファイル
1GB分があなたの手元に!
ところで、Vectorにあるような素数列挙ソフトと比べるとどう?
素数xpとか。
そりゃ全然かなわないよ。
1兆も計算出来るという事は 37bitの計算が出来るわけだし。

こんな方法はどうだろ?
上で出てる2,3の倍数を除く手法を拡張して、N迄のすべての素数の倍数を除くコードを
吐き出すプログラムを作るというのは
>>359
>>113が近い?
OO さいこー!!
            _____________
   ∧,,∧    /
  _ ミ,,゚Д゚彡 _< unsinedint最大まで求めるってのは
.=| |=U===U=| |= \いいかもしんない
 | | .ミ   ミ | |     ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 | |ノ∪''∪. | | しかし…もう篩いの容量が
         劇的には減らないですねー

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

171億 7986万 では?
            _____________
    ∧,,∧    /
  _ ミ,,  彡_<  ゲーム脳で頭が腐ったみたいです。
.=| |=ミ   ミ=| |= \
 | | ミ@ ミ | |     ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 | | ∪''∪ | | 鬱だ。
 | |      | |
          
2^32 -1 迄のは >>324で出るようだが?
366デフォルトの名無しさん:02/11/08 11:53
篩の結果を 算術圧縮したらどうなるんだろ?
圧縮する時の係数を n bit目を 1/log(n) としたら、ほぼ完全な乱数になるのだろうか?
367デフォルトの名無しさん:02/11/08 20:05
おいデルフサー
てめーああん?


カワイイじゃねえか、乳揉むぞコルァ
>>362
一気に計算する必要はないんよ。
過去ログにそういうアルゴリズムがあった。
369デフォルトの名無しさん:02/11/09 01:15
>>362
Del使ってないからわからんのだがunsinedintってなに?
unsignedintの親戚かなにかか?
>>369
もう★ そんな野暮なこと聞くなんて
おちゃめさんなんだからぁ♪
            ∫    _________
   ∧,,∧     ∬   /
   ミ,,゜Д゜彡っ━~  < 安心Edintを知りませんか?
_と~,,  ~,,,ノ_.  ∀   \ 
    ミ,,,,/~), │ ┷┳━   ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ .じ'J ̄ ̄| ┃
 ̄ ̄ ̄ ̄ ̄ ̄ ̄  ┻

       ∫         _____________
   ∧,,∧ ∬       /
   ミ,,-Д-ノ,っ━~  < ・・・ 俺も知らない・・・
_と~,,,  ~,,,ノ_. ∀   \
    .ミ,,,/~),  .| ┷┳━   ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ .し'J ̄ ̄|... ┃
 ̄ ̄ ̄ ̄ ̄ ̄ ̄   .┻
>>368
使わない所の古いはHDに退避させとくのですか?
速度とかの辛味で難しそうですね。
>>126 のソースコードの作者だけど、Delフサギコ さんのソース良さげな感じ。
そのうちアイディア取り入れさせて貰います。

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

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

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

ただし、

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

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

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

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


# ……最近某所で、キャッシュを有効にするための凄まじい方法も聞きました。
>>372
あのリンク貼った者です。まさか降臨なされるとは。
   すごいっす。
     .Λ,,Λ.  ___  
    ミ;゚Д゚ミ .||::::::::||
    ミ   つ___||_____|| 
   | ̄ ̄|__ミ―――――
   `ー┬‐''
     ┴
>エラトステネスの篩いにおいて、ある数Nが合成数かどうか知るためには
>√Nまでの素数リストがあれば十分です。

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

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

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

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

結局、97が素数って判定した後は
それをどこかメモリに貯めておかなければならないのかな???
いや、、求めた瞬間にファイル出力したらいいのか...
     わけわかなくなってきた。
     .Λ,,Λ.  ___  
    ミ  ,,彡 .||::::::::||
    ミ   つ___||_____|| 
   | ̄ ̄|__ミ―――――
   `ー┬‐''
     ┴
私のコードは2147483647までの
素数篩いはメモリ上に構築可能なので(90MBもあるけど)
それを利用して
2147483647*2147483647=
4611686014132420609
までの値が素数かどうかはわりと、はやく判定できるのかな。

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

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

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

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

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

2,3,だけじゃなくて、5,7,11も抜きたいけど,,,
いったい、どうやるんだろかしら、、、、まだまだ奥深いです。
落ち着け。
378372 ◆2ZUH6PwhYk :02/11/09 20:47
どうも言葉が足りなかったようで、分かりにくくてすみません。
>>376で仰ってる通りの感じです。

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

# この文も直さなきゃなー。
# 「3,5,7の倍数を除いても無駄」とか書いてあるし。
# 昔、試したところでは確かにあまり効果が上がらなかったんだけれど、
# このスレ見てる限りではどうも私の実装が腐ってただけみたい。
            _____________
   ∧,,∧    / 試行錯誤したり
   ミ,,゚Д゚彡 <  実装したりして、いろいろ
   ,;゙   ミ     \ わかってくるものっすね。
 @ミ,,,UUミ       ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄

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

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

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

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

380デフォルトの名無しさん:02/11/10 18:17
>>379
高速化するなら >>324のようにしなくちゃね。
0〜(2*3*5*7*11-1) で1と 2.3.5.7.11以外の素数のある個所を除いたテーブルを用意して
それを篩のビットを消す時に使うようにする。
381Delフサ:02/11/13 22:22

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

最後はこんなんであってるかな?
4294966997 4294967029 4294967087 4294967111 4294967143
4294967161 4294967189 4294967197 4294967231 4294967279 4294967291
あってるみたいだね。おめでとう。
しかし30時間もかかるもんなのか…
保守っとく
  ,,,,,,,,,,,,,∧,,∧   /IntToStrで普通に数値を文字列変換して
〜′,,,,,,,ミ,,゚Д゚彡< 追加ってるから、めちゃ遅くなってるですね。
  UU""" U U   \
        その辺りを高速化する気にはならなかったです。

なんか、D7からIntToStrがアセンブラになったとかならないとか。
TBitsのメモリイメージをバイナリファイルで保存できたら
面白いかもしれません。
(それでも数十MBのファイルはあまり扱いたくないかな。)      
385デフォルトの名無しさん:02/11/20 00:47
、、以下2をのぞて
・2の倍数は素数ではない、つまり素数は奇数でなければならない
・素数(奇数)と素数(奇数)を足すと素数ではなくなる
・素数の1以上の倍数は素数ではない eg: 13*2=26 13*3=39->39/3=13
素数の2乗を6で割った余りは必ず1である

なんてね。>>385はうまいネタでも思いついた?
387誰か:02/11/20 13:39
50000までの素数を求めるプログラムをCで組んでくれませんか? おながいします
ごめん、日本語の読めない厨房をここへ誘導してしまいました
回線切って、首釣ってきます...
389デフォルトの名無しさん:02/11/20 14:10
>387よ、おまえにお似合いのプログラムを書いてやった
早くこのプログラムを提出しろ。

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

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

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

   if (flag==0)
    printf("%lf\n", i);
  }
}
390誰か:02/11/20 14:29
ありがとぅございました
391Warez:02/11/20 15:57
セミコロン1つくらい省略しておけばよかったのに・・.
392誰か:02/11/20 16:01
厨は逝けや
>>392
オマエガナー
394デフォルトの名無しさん:02/11/21 00:49
define(`genprime',`ifelse($#,1,`genprime(2,1,$1)',
  `ifelse($1,$3,`(total decr($2))',`ifelse(chkprime(1,$1,$2),1,
      `$1 define(`prime$2',$1)genprime(incr($1),incr($2),$3)',
      `genprime(incr($1),$2,$3)')')')')dnl
define(`chkprime',`ifelse($1,$3,1,`ifelse(
  expr($2%prime$1),0,0,`chkprime(incr($1),$2,$3)')')')dnl
genprime(1000)
高速化&圧縮
define(`era',`ifelse($1,$2,`(total $3)',`ifdef(`sym$1',`era(incr($1),$2,$3)',
`$1 fill(eval(`$1*2'),$2,$1)era(incr($1),$2,incr($3))')')')define(`fill',
`ifelse(eval(`$1<$2'),1,`define(`sym$1',)fill(eval(`$1+$3'),$2,$3)')')define(
`primes',`era(2,$1,0)')primes(10000)
2^32-1までの素数をファイルに出力するのに、
AthlonXP 1800 メモリ 512MB で 2分50秒くらい
Pentium2 400MHz メモリ 128MB で 14分くらい
ってどうですか?
>>396
健闘してるんじゃない? >>150といい勝負かも

ファイル出力込みの時間はディスクの状態によって結構変わる
測定前にデフラグをかけるとよろし
398396:02/11/22 23:32
>>397
FreeBSDだからデフラグは関係無いみたいです。
あと、150とは全然比較になりません。
そもそも多倍長整数が扱えませんし。
多倍長整数ってすごく難しそうなイメージがあります。
>>394-395
なんだこりゃ?
400デフォルトの名無しさん:02/11/23 14:25
最速ハケーン!
http://www.crt.or.jp/~kokochi/sosu.htm

>MMX Pentium 150 MHz のパソコンで、 0 ≦ 整数値 ≦ 4,294,967,295
>の全素数 203,280,221個をカウントするのに、約 16 分を要する。
401デフォルトの名無しさん:02/11/23 14:41
うえーんPrologで自己展開形式素数計算プログラムキボン( ●Д●)
402デフォルトの名無しさん:02/11/23 16:13
>>400
天進法かよ!
>>400
それは知っているよ。
404403:02/11/23 17:46
小さい方からの素数の最少公倍数ごとに区切っていくものでしょ。
405403訂正:02/11/23 17:52
少=>小
なんでこんなバ化なんだ家の辞書(バ化だって・・・TOT)
406403:02/11/23 17:55
>>400を使った場合、
この前発表された公式と、どう比べたら良いのか、詳細希望。
>>406
「この前発表された公式」と言うのはインド人が見つけたアルゴリズムのこと?
>>407
そうかもしれない。あっちは素数一つを求める事が出来るとかか?
409408:02/11/24 16:05
[列挙]が付いているからな、
このスレタイには
判定のほうは随分前にdat落ちしたからね
411396:02/11/25 15:51
改良した結果、2^32-1までの素数を計算するのに(正確には203280221番目の素数を計算するのに)
AtholonXP 1800 で 40秒台
Pentium2 400MHz で 3分30秒台
まで縮まりました。ファイル出力は無しです。
>>411
ファイル出力ありの記録希望
413396ではないが:02/11/25 22:06
ファイルシステムが違うので、比較不能と思われ
414396:02/11/25 23:21
もうちょっと改良したところ、ファイル出力なしだと、
Athlon で 35秒、
Pentium2 で 3分20秒、
ファイル出力ありだと、
Athlon で 2分ちょうど、
Pentium2 で 9分ちょうど
ぐらいでした。
415396:02/11/25 23:30
途中で、関数は全部マクロで書いたほうが速いことに気付いたのですが、
ファイル出力関連はめんどくさくて直してなかったので遅いです。
あと、n を p で割った答を a ,余りを r に代入するのに、
r = n - (a = n / p) * p;
とかしてたんですけど、普通に
a = n / p; r = n % p;
と並べたほうが速い(ほとんど変わらないけど)ことに気付きました。
コンパイラが最適化してくれるのでしょうか。
アセンブラを知らないので、内部的なことがよく分かりません。
ソースきぼん
417 ◆2ZUH6PwhYk :02/11/26 02:13
>>415
除算命令は余りも同時に求めてくれるから、そのせいだと思います。
aを計算した段階で、rの値もレジスタに入ってるので。

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

私もソースきぼん。
418 ◆2ZUH6PwhYk :02/11/26 02:14
× ご丁寧に除算してくれてたけど。
○ ご丁寧に二回除算してくれてたけど。
419396:02/11/26 12:28
http://tool-ya.ddo.jp/2ch/trash-box/file/20021126122038042.c
人に見られることを意識していないので、死ぬほど汚たないです。
変数名一文字とか、変数使い回しとかいっぱいあります。
そのままだとファイル出力しないので、print_integerのコメントアウトを
二箇所はずしてください。fopenなのであらかじめprime.datというファイル
がないといけないかもしれません。ファイルは2G超えるので注意して下さい。
420396:02/11/26 12:31
>>417
そうなんですか。レジスタとかよく分からないけど。
コンパイラは gcc 2.95.3 です。-O3をつけてます。
VCだとコンパイルできないのね
1億まで(ファイル出力あり)
>>324 52秒
>>419 50秒
K6-2 400MHz
423396:02/11/27 02:23
324の 0x20010000 はどこからきてるんだろう。
(n/6)*4+3 は (n*2-1)/3
(n/6)*8+1 は (n*4-1)/3
でもいいですね。
424デフォルトの名無しさん:02/11/27 07:56
ほんとは
0x20000000+0x10000/8 でいいのかな?
余裕を取っただけでは?
425396:02/11/27 14:41
unsigned char * MakePrime32bit( void )
{
const MAX3=0x55555555;
unsigned char * tbl = malloc(0x20010000/3);
unsigned int n=5,m=1,n1,n2, d;
memset(tbl,0,0x20010000/3);
n1=3,n2=10,d=8;

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

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

return tbl;
}
426396:02/11/27 14:47
計算量を減したはずが、逆に遅くなりました。
なんでなんだろう。
あと、ここのプログラムはどうなんでしょう。
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
>>425は毎回 n1,n2類の計算をしてるけど>>324は素数の時だけしてるからでは?

高速にするなら
1、SetBit を展開して高速にする
2、2つの倍数消しを順にではなく交互にする >>308
428396:02/11/27 18:08
unsigned char * MakePrime32bit( void )
{
const MAX3=0x55555555;
unsigned char * tbl = malloc(0x20010000/3);
unsigned int n=5,m=1,n1,n2, x;
memset(tbl,0,0x20010000/3);

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

return tbl;
}
429396:02/11/27 18:13
>>427
確かにそうですね。でも428でも遅いんですけど、なんか間違ってるかなあ。
単純に、アライメントが変わったからじゃないの?1割2割は命令の配置番地で変わってしまうよ。
431デフォルトの名無しさん:02/11/29 23:59
参戦♪
と言う訳で32以下の素数と、それ以上の素数を分けて篩いました
gcc2.95 オプション -O でコンパイルして K6-233(←CPU遅すぎ) で
2^32-1 までの素数を数えるのに4分弱でした

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

http://tool-ya.ddo.jp/2ch/trash-box/file/20021129234010029.tgz
アスロン1700+で1億まで求めたら24分かかった・・・
( ゚д゚)ポカーン
433432:02/11/30 19:32
改良しても7分半かかった・・・
( ゚д゚)ポカカーン
ただいま作成中・・・。
435431:02/12/01 00:25
>>432
main()の
for ( n = 1 ; n < 65536 ; n += 1 ) {}
nの値を1億に変えてませんか?
分かり辛いですが、このままで 2^32-1 までを求めてます
436431:02/12/01 00:35
>>432
直接1億にしたら、もっと時間が掛かりそうですね…
取りあえず、各値を変えないで、実行してみてください
437432:02/12/01 06:09
>>431
すいませんその時間は私が自分で作ったヤツのです(ウン子すぎ)。
(6n±1 を sqrt(6n±1)までの素数でひたすら割るもの)
2^32-1 までで4分っすか・・・早いですね。
438他スレの297:02/12/01 14:32
畜生・・・VBで組んで、10万までは3秒、100万までは1分29秒・・・。
100万まで1秒切れるというのはマジすか???
>>438
最適化のオプションをいじくるとか
440123:02/12/01 15:20
VB最強ってことか・・。
419から5の倍数も除いたもので、
AthlonXP 1800 で 20秒
Pentium2 400MHz で 2分11秒
ぐらいでした。
443他スレの297:02/12/01 17:07
改良して10万なら2秒。100万までなら43秒・・・(VBで)。
>>441のものには全然敵わない・・・くそ!!!
444432:02/12/01 17:19
>>443
もしかして除算型のアルゴリズム使ってない?
エラテネシのほうが早いよ。
445他スレの297:02/12/01 17:33
エラテネシって何すか?
検索したけれども・・・ない。
>>445
エラトステネス
447デフォルトの名無しさん:02/12/01 17:57
  ( ・∀・)   | | ガッ
 と    )    | |
   Y /ノ    人
    / )    <  >__Λ∩
  _/し' //. V`Д´)/ ←>>444
 (_フ彡        /
448432:02/12/05 13:44
1億まで求めるのに3分45秒まで短縮できたけどもうだめっぽい。
次はエラテネシでやってみようかのぅ・・・
保守
450デフォルトの名無しさん:02/12/10 20:30
これやるとエラーが出る・・・。
ちなみに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;
}
}
}
//続く
451450:02/12/10 20:31
//続き
for(i=2;i<=k;i++){
for(j=2*i;j<=l;j++){
if(j%i==0){
p[j]=0;
}
}
}
for(i=2;i<=l;i++){
if(p[i]==1){
fout << i << '\n';
m=m+1;
}
}
cout << "素数は全部で" << m << "個です" << '\n';
fout.close();
return 0;
}
452450:02/12/10 20:32
>>451は間違い。こっちだった。
//続き
for(i=2;i<=l;i++){
if(p[i]==1){
fout << i << '\n';
m=m+1;
}
}
cout << "素数は全部で" << m << "個です" << '\n';
fout.close();
return 0;
}
これは遅いですか?

#include <stdio.h>
int main()
{
int i,j,k;
for(i=2; i<100000000; i+=(i==2)?(1):(2))
{
i+=(i%3)?(0):(2);
for(j=2; (double)j<sqrt((double)i); j+=(j==2)?(1):(2))
{
if(!(k=(i%j))) break;
}
if(k){
printf("%d\n",i);
}
}
scanf("\n");
return 0;
}
>>453
除算型の中でも遅い方だと思う。
455デフォルトの名無しさん:02/12/12 04:38
>>453
Cのコンパイラ持っていないので分かりません。
どれぐらい時間かかった?
2、3日かかりそうで怖いな
457デフォルトの名無しさん:02/12/12 22:25
知ってたらすまそ〜ん。
今日会社で仕事中に思いついたいい方法を書くよ〜ヒントだけど。
(ちなみにオイラはこの方法でしこたま短縮した)

1.「整数乗余」演算子を使わない(C/C++なら%、VBならMod)
2.エラストテネスのふるいをやる。

この方法でしこたま速くなる!!!
>>457
しこたま速くなるんじゃなくてしこたま遅かったんだろ。お前のが。
459デフォルトの名無しさん:02/12/12 22:31
全然進歩しないね
これが2chの限界
460457:02/12/12 22:32
>>458
そうだよ。
>>459
お前に言われたくない。
461デフォルトの名無しさん:02/12/12 22:35
エラトステネス以上のアルゴリズム、誰か知らない?
>>457
>1.「整数乗余」演算子を使わない(C/C++なら%、VBならMod)
%ではなく / を使えということ?
463デフォルトの名無しさん:02/12/12 23:03
>>457
このスレを最初から読むことを勧める。
>>461
あったらいいなぁと思う今日この頃。
464デフォルトの名無しさん:02/12/13 04:44
下記のプログラムは素数を出力するのですが、
本当に素数が出力しているのか自信がありません。
どなたか試していただけませんか?
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000
int main(void)
{
int s[] = {2, 3, 5, 7};
int ss[MAX] = {0};
ss[0] = 1;
ss[1] = 1;
for(int i = 0; i < 4; i++){
int n = s[i] + s[i];
for(int j = 0; n < MAX; j++){
if(ss[j] != 1){
ss[n] = 1;
n = n + s[i];
}
}
}
for(i = 0; i < MAX; i++){
if(ss[i] != 1){
printf("%10d", i);
}
}
printf("\n");
return 0;
}
素数って上限の有無はまだ確定してないですよね?
>>465 無限にあることが証明されている。
なるほど。
つーことはリストに照らし合わせる必要がある限り、
無限のメモリが必要か。

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

予想はできてるんですか?
468デフォルトの名無しさん:02/12/13 05:38
そんなこと考えるよりさ
漏れたちでエラトステネスより
オーダの小さいのアルゴリズムを
考え出せばいいのさ
469464:02/12/13 05:43
>>467
勉強の為に作っただけなので、とりあえず1万桁でいいです。
470デフォルトの名無しさん:02/12/13 05:44
そいやどこかに、今のスパコンでどのくらいかかるか出ていたっけ。
ってことは、おおよそ見当はついているのか。

力業が通じるかどうかってことなんだ。
471デフォルトの名無しさん:02/12/13 05:49
素数の判定に他の素数との割り算を必要としないアルゴリズム?
472457:02/12/13 18:26
>>471
だから、割り算をすると遅くなるんだよ。
発想の転換をしようや。
エラトステネスのどこに割り算を使うんだ?
474デフォルトの名無しさん:02/12/13 19:51
>>472
このスレ全部読めよ
>>473
任意のn〜mまでの素数を列挙する時じゃねえか?
>>475
フルイを作っていけば勝手に出来るだろ
477俺(数学者崩れ):02/12/14 15:43
俺の現況:
VBでテキストファイルに入力しない場合は
100万以内の素数を調べるのに平均0.7秒台
テキストファイルに入力すると平均1.1秒台。

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

>>441のVB製に勝ててないが、俺は2の倍数を初めから除いていない。
ちゃ〜んと2の倍数を消すところから計算スタートしてるの。
478デフォルトの名無しさん:02/12/14 15:53
いま分かっている最大の素数。約405万桁。
http://www.mersenne.org/prime5.txt (デカイのでナローバンドな人は注意!!)
おそらく↑の平方根までの素数は出尽くしてるかと。
480俺(数学者崩れ):02/12/14 16:17
>>477
ミスった。VBでファイル出力しないと0.66秒台
ま、大した事無いが・・・。
>>477
VBはちゃんと最適化してるか?
482俺(数学者崩れ):02/12/14 16:41
>>481
幾ら探してみても俺のVB6.0には最適化オプションが無い。
参ったね♪
アカデミック版とか?
>>476
2^32 〜 2^32 + 2^31 のように大きな数を列挙する場合は
除算を使った方が良いだろ
あぁ、確かに2、3回除算使ってるな>範囲列挙
>>457も分かってないが>>485も何処で必要になるか分かってないだろ
>>486
黙ってろ表六玉

ここ更新したんやね
http://www.gt.sakura.ne.jp/~nyagy/integer/sosuu.html
488デフォルトの名無しさん:02/12/15 12:11
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
const int Max=1000000;
bool p[Max+1];int a,b,c,i,j,k,q;
int main()
{
long clock_t;clock_t clock();j=1;k=0;q=2;

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


489488:02/12/15 12:13
//続き
while(p[q+j]==0){
j=j+1;
}
q=q+j;j=1;
}
     for(i=2;i<=Max;i++){
if(p[i]==1){
//fout << i << '\n';
k=k+1;
}
}
b=clock()/1000;a=b/360000;c=clock()-b*1000;
     cout << "素数は全部で" << k << "個です" <<'\n';
cout << "所要時間は" << a << "分" << b << "." << c << "秒です" << '\n';
return 0;
}
//かなり速いと思うが、どうよ?
つーか過去ログ読んでないやつ多すぎ。
324(関数部分は428でも可)ぐらい、短いんだからすぐ読めるだろう。
491デフォルトの名無しさん:02/12/15 15:49
>>490
お前は何も解っていないんだな???
2と3の倍数を最初から除いておいて何の意味があるんだ???
だったら5も7も、11も最初から除いておけよ。
アルゴリズム、って意味を知ってるか???お馬鹿ちゃん。
>>491
どのコードのどの「アルゴリズム」が324より優れているのか説明キボン
>>490
同意。
>>491
何で必死なの?
494デフォルトの名無しさん:02/12/15 18:36
>>491
アルゴリズムをそっくりそのまま使う人ですか?
2の倍数を最初から除くのはアルゴリズム的には無意味。
フルイの処理のループを一回最初っから実行しているのと同じ。
確かに処理として速くなるが、それならすべての素数を出した状態からスタートすればいい。

そう思った、小学5年の夏。
>>495
勘違いですね
>>495
意味不明
498デフォルトの名無しさん:02/12/15 19:18
ここですか。
「アルゴリズム」の意味を理解していないデジドカの集うスレは。
>>496 >>497
馬鹿二人(藁
500デフォルトの名無しさん:02/12/15 19:31
>>495
もう少し分かりやすく説明してもらえると・・・
>>495
たしかに2や3が最初から素数かどうかなんてコンピュータはわからないわけだから
アルゴリズムとしてはおかしい
けど実践的なのは事実
>>501
それをアルゴリズムの間違いとするのは、おかしいだろ?
「アルゴリズムのクラス(or プロパティ)として、ユニバーサル性を欠く」
ということなら、わからないでもないが。
503501:02/12/15 19:34
× それをアルゴリズムの間違いとするのは、おかしいだろ?
○ それをアルゴリズムがおかしいとするのは、間違いだろ?
504502:02/12/15 19:34
たびたびすまん。503は502である。
505495ではないが:02/12/15 19:36
アルゴリズムを追求するのであって、小手先のテクニックを
追求するのではない。
2と3の倍数を初めから除いたアルゴリズムと、そうではなく
2から始めて3の倍数を消した後から、この二つのアルゴリズムを比較して、
速い方が優れているアルゴリズムなんだよ。
アルゴリズムとはそういうものなんだ。
>>505
2の倍数、3の倍数を省けば、メモリ使用量は 2/6。メモリ使用量は 4/6 減る。
5の倍数も省けば、 8/30。さらに、2/30 減る。
7の倍数も省けば、 43/210。さらに、13/210 減る。
11の倍数も省けば、 339/2310。さらに、134/2310 減る。
効果は徐々に薄くなっていくが、計算量は増えるから逆に遅くなる。
アルゴリズム的に無意味か知らんが、5の倍数くらいまでなら明らかに速くなるよ。
言いたいことは分かるが、小手先というにはあまりに効果的。
エラトステネスってあんまり工夫できないから、こういう事するしかないのよ。
>>505
意味不明な言葉で誤魔化さないようにしましょう。
>>505
速い方が必ずしも優れているアルゴリズムでないことはわかってます?
もちろん速度が最重視される分野ならばそれで良いことも多いのですが。

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

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

まあ、ぶっちゃけ何でもいいよw
>>508
予め2と3と5の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。
511505:02/12/15 19:43
>2と3の倍数を除くアルゴリズムは

これはアルゴリズムではなく、プログラムだろ。
>>510
予め2と3と5と7の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。
513デフォルトの名無しさん:02/12/15 19:44
>>505
小手先のテクニックを追求して、アルゴリズムに反映させるから、
より速く・優れているアルゴリズムができるのでは?
>>512
予め2と3と5と7と11の(以下略
あらかじめ○○の倍数を除くアルゴリズムの中で優れてる奴きぼんぬ
2はともかく大きな数になると取り除くのにも色々方法がでてくる
>>509
単にユニバーサルかそうでないかの問題。

ユニバーサル性を重視するなら、「素数の定義」しか使ってはいけない。
しかし、多少のユニバーサル性を欠如させても、それ以上の効果があるならば、
分野によってはそのアルゴリズムの方が優れているといえる。
特に素数を求める場合は、2や3,5の倍数を取り除くことは当たり前にできる上に、
素数を求める目的から、その程度のユニバーサル性は必ずしも必要ない。
gifの解凍アルゴリズムを小手先のテクニックで改良したら
新しいアルゴリズムになってライセンス料支払わなくてよくなるかな?
>>516
2や3,5の倍数を取り除いてもアルゴリズムは同じです。
519デフォルトの名無しさん:02/12/15 19:48
予め2と3と5と7と11と13の(以下略
520506:02/12/15 19:49
505へのレスっておかしかった。前半だけ読んで勘違いしてたスマソ。
>>516
2や3や5の倍数を当たり前に取り除けるのは何故ですか?
2や3や5が素数だからですか?
2や3や5が素数であることを求める処理を省いていいんですか?
>>517
gif が問題になるのは LZW (> LZ78) を使っているから。
従ってLZWさえ使用しなければ問題ない。
しかし、LZWを別のアルゴリズムに置き換えたgifはもはやgifではない。
(一応、LZWを使わずにgifを実装できるが、遅すぎて使いもにならない)
誰か2,3,5・・・の倍数を取り除くのを自動化できない?
面倒だから作るのいやなんですよw
524デフォルトの名無しさん:02/12/15 19:51

http://petitmomo.com/mm/

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

めぐ(^o^)-☆
>>521
多分>>516のいいたいことは、ユニバーサル性がどこまで重視されるか、の違いだけ。
立場が違えば解が違う。それだけ、だと思う。
まぁ考え方(素数列挙に対する姿勢?)の違いなわけで。
素の状態からの素数探索を追求する人も
ひたすら爆速素数列挙を目指してる人も
マターリしませうヽ( ´ー`)丿

2と3の倍数を除外する以外にも過去ログではいろんなテクニックが使われてるし。
素数を求めるので無くて、
素数じゃないのを求めてそれを省くとかするアルゴリズムはどう?
>>527
それがエラトステネスの篩なわけで・・・
529  :02/12/15 19:54
>>526 結局ふるいを人間と共有しているのであって、単にふるいの話だけのような気もしました。
>>527
しね
>>529
人間の知識を与えるアルゴリズムを非ユニバーサルというらしいですね。
>>517
既にsusie用のgifプラグインとかそうしてる。
533  :02/12/15 20:07
>>531 や、人間の知識も自然な派生(アルゴリズムであれ)だと思うので・・・
とりあえず324がエラトステネスの基本形。
5の倍数も省けば速くなるかも知れんが、劇的に速くはならない。
ただ、メモリ一発でやっているので限界があるし、速くない。
だから、分割して篩うことを考える。
すると、分割されたメモリが一周するごとに計算が必要になる。
差がつくとしたらそこ。ほとんど小手先の塊みたいなもんだよ。
分割して篩う方法は>>378>>487など。
たしか>>419も分割してた気がするけど…
× エラトステネスの基本形
○ 分割しないエラトステネスの基本形
でした。
>>531
人間の知識っていうかこの場合は答えだからなぁ。
答えを入れれば答えを出すのが速いのは当たり前だし。
538488:02/12/15 20:29
>>535
オイラのも入れろ!!!
>>538
分割してないじゃん
http://idm.s9.xrea.com/factorization/eratosthenes.html

ここの「アルゴリズムの基本」ってところとその証明、残念ながら
厳密には間違ってるよw
学会の糞偽善者どもは、さり気なく情報を訊き出しては、
行く先々にあらゆる人材を送り込み、偶然を装っては
チンケな猿芝居やコザカしい罠、悪質な嫌がらせを次々と仕掛けてくる。
その、あまりにも回りくどく分かりにくい嫌がらせの手法で、
実際、気付くのに五年以上かかった。普通はまさか?と思うものだ。
だが偶然ではなかった。全て計画的に仕組まれたものだった。
あくまでも偶然を装ってである。何とも白々しく腹黒く悪質で陰険なことか!
こっちが気付かない、或いは知らん振りしてると、しつこく睨み続けてくる。
こっちが気付き不快感をあらわにすると、知らん振り。
頭にきて攻撃すると、散々自分から仕掛けて来ておきながら、
いかにも自分が被害者ぶるのである。
たとえ地元から遠く離れていても、である。
前以って嫌がらせを組織や会場にに潜り込ませたり、
あらかじめ通過地点に嫌がらせを配置・待機させる事もある。
一体奴らは何がしたいのか?気に入らないならダイレクトに来い!
被害妄想と思うかもしれないが、そうする事で
今までの不可解な出来事の全てにおいて、つじつまが合うのである。
偽善者という言葉は奴等の為にある。
学会のあるクソ信者と一緒にいると、
必ず初対面の人間からも頭ごなしに白い目で睨まれる。
明らかに年下の人間も俺を見下した目で見ている。
「あいつはロクでもないガキだ!」とでも吹いて回ってるんだろう。
表面上は親切ぶっていても、裏で糸を引いているのは奴等である。
正に偽善者と呼ぶに相応しい。
いつでも助けてやるよ!と言いながら、足を引っ張っているのは奴らだ!
偽善スマイルの裏では、腐ったはらわたがドス黒く渦巻いている。
学会の人間に心を開いてはいけない。
自分の知らない同一人物が目の前に度々現れたら要注意である。
>>541
お見事な縦読み
543475==484==486:02/12/15 23:21
>>487
nからmまでの素数を求める時に篩を始める位置は
√n未満の素数(p)の場合は
((n-1+p)/p)*p
√n以上√m以下の素数(p)の場合は
p*p
>>485で列挙範囲と言ってるのだから
最初から2・3・5等の素数を省くのに必要な除算は関係無い
要するに、これでは除算は√n以下の素数1つにつき1回除算が必要なのに
>2、3回除算使ってるな
と言ってる>>485は分かってない
つーか、それが分からないのなら、お前が黙ってろや>>487
           _____
   ∧,,∧∩  /
  頒゚Д゚;彡< 除さん、いらんのですかい!
    ,;゙⊃,ジ   \_____
 〜ミ ,,○
    ∪     しらかた。

なんかコムズカな話ばかりでよくわかなんですが…

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

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

 Result := DivBuffer*48; //1..210/211..(210*2)の間に48つの素数がある
 case ModBuffer of
   1..10:Result := Result + 1;
  11..12:Result := Result + 2;
  13..16:Result := Result + 3;
  17..18:Result := Result + 4;
  19..22:Result := Result + 5;
  23..28:Result := Result + 6;
あと、略
>>543
それではお手並み拝見。
>>544
任意のnからmまでの範囲の素数を列挙するのに
除算は1回必要ですが、それに対して
>>485が>あぁ、確かに2、3回除算使ってるな>範囲列挙
と書いてるので分かって無いと書いただけで
2・3・5等の素数を、省いて篩う場合には必要です
と言っても、そのコード読めないので
そのコードが正しいかは分かりませんが…
547485:02/12/15 23:57
>>543
うひぃ、怒られた。
適当なコト言ってすまぬ。>>543の言うとおりです。

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

キュピィィィン   +   /
     ∧,,∧   < よくわかりますた
    ミ,, ゚Д゚ミ .  \>>546さん
    ミ  つ つ ))
 +   ミ ⊂.ミ
     ''∪''''
ところで、2,3,5,7,11ぶち抜きコードはわかるんですが
篩い繰り替えし使いのやり方はわからないので
ここのサイトは
http://www.gt.sakura.ne.jp/~nyagy/integer/sosuu.html
よい、勉強になります。

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

>>548さん
そうなんですが、次の11を求めようとすると、
2*3*5*7*11で、2310まで
篩いに落ちるのを、目で見てソースに落とすのを
考えると鬱るので、まだやってません。
>>549
その部分を自動で適当に作ってくれるプログラムを作るとか…
ついでに、そのリンク先ですが、確かに分かりやすいですけど
遅い原因はprintfもそうですが、やってる事にも無駄が多いですよ…
分割して篩いたい時は、まず√nまでの素数を普通に篩って配列にし
その配列を使って篩った方が早いです
int main () {
  char buf[1024];
  int prime[54],mod[54];/*256までの素数の数*/
  int i,j,last,base,ed,size;
  last=0,base=256,ed=65536,size=1024; /*sizeはbufのサイズ*/
  for(i=0;i<base;i++) buf[i]=0;
  for(i=2;i<16;i++){
    if(buf[i]==0){
      for(j=i+i;j<base;j+=i) buf[j]=1;
      prime[last]=i;
      mod[last++]=j-base;
      printf("%d\n",i);}}
  for(i=16;i<base;i++){
    if(buf[i]==0){
      prime[last]=i;
      mod[last++]=i*i-base;
      printf("%d\n",i);}}
  while(base<ed){
    if(size>ed-base)size=ed-base;
    for(i=0;i<size;i++) buf[i]=0;
    for(i=0;i<last;i++){
      while(mod[i]<size){
        buf[mod[i]]=1;
        mod[i]+=prime[i];}
      mod[i]-=size;}
    for(i=0;i<size;i++) if(buf[i]==0) printf("%d\n",i+base);
    base+=size;}}
552551:02/12/16 02:33
文句ばかり言ってても、しょーも無いので
分割して篩うためのサンプルを書きました
適当に書いたので2の倍数も篩ってますが小さい素数を対象から外して
無駄(下から3行目のmod[i]-=sizeとそのwhileの条件等)も省いていけば
それなりに高速になると思います…が
>>426のリンク先が、マジで早いですよ…
バグがあるのか仕様なのか、2^32-1までの素数は篩えませんでしたが
2^32-10位の数で篩った時の早さは、自分が手を尽くせるだけ
尽くしたものに比べて2.5倍程早かったです(両方とも出力なし)
多分switchとcaseを連発して、7以下の素数を除外すれば
その差をかなり縮められると思いますが…
まぁ、>>426を試して、やる気を無くさなかった方は頑張ってみて下さい
>>544
それは、その部分を関数にして処理しようとするからそうなるんで、
高速化したいなら配列 を作って状態遷移型に処理させるといい

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

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

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

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

閑話休題;
>>549
> 2*3*5*7*11で、2310まで
> 篩いに落ちるのを、目で見てソースに落とすのを
> 考えると鬱るので、まだやってません。
Perlerみたいなことを言うけれど…、そのソース(てか素数源ふるい表)自体を
プログラムに作らせちゃったほうが早くて正確じゃないですか?(´・ω・`)
初期化段階で*11までの表を計算させちゃって、あとは2310の倍数単位
ループ内で、例外をふるってく…と。
#この手だと13までは苦でなさそう。
まあ今のパソコンのCPUだと除算も1クロックな時代だから必要ないけど
一昔前は >>554の通り 除算は遅かった。

その頃は、 a/b で bが素数程度に連続して除算するならニュートン法を使う
なんて手も有効だった。
>>553
nまでの素数を求めたい時に必要な素数は√nまでの素数p
それらの各素数pがマークを付け始めるべき位置はp*p
だから、その最初の位置を決める時にp/2310の除(余)算が必要なんだって

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

while(i<MAX){
int tmp;
System.out.println("テーブル更新 次の更新は "+changeTable + ", 前の更新は "+ savedCurrentBaisuu);
//テーブルの更新条件
while(i<changeTable && i<MAX){
tmp = currentBaisuu+1;
if(chkSosuu(tmp)){
end.next = new Sosuu(tmp);
end = end.next;
System.out.println(currentBaisuu+" + "+1+" = "+end.number);
}
do{
tmp = (i=currentBaisuu+current.number);
if(chkSosuu(tmp)){
end.next = new Sosuu(tmp);
end = end.next;
System.out.println(currentBaisuu+" + "+current.number+" = "+end.number);
}
if(current == Sosuu.isEnd)break;
current = current.next;
}while(i<MAX);//リストに追加していく
current = newFirst;
currentBaisuu += savedCurrentBaisuu;
i=currentBaisuu;
}
559デフォルトの名無しさん:02/12/16 20:38
//テーブルの更新
currentBaisuu = changeTable;
savedCurrentBaisuu = changeTable;
Sosuu.isEnd = end;
newFirst = newFirst.next;
current = newFirst;
changeTable *= newFirst.number;
}
}
boolean chkSosuu(int tmp){
Sosuu localCurrent = newFirst;
int rootNumber = (int)Math.sqrt(tmp);
while(localCurrent!=null && rootNumber>=localCurrent.number){
if((tmp%localCurrent.number) == 0){
// System.out.println("Err And kill at "+tmp);
return false;
}
localCurrent = localCurrent.next;
}
return true;
}
}
class Sosuu{
Sosuu next,before;
int number;
static Sosuu isEnd;
Sosuu(int i){
number = i;
}
}
javaですまないがテーブルを自動で増やしていくプログラム
アルゴリズムは
6までは最初から用しといて
30を目指して
(1または5)+6 *n()
の数に対してチェックしていく
30になったら
つぎは210になるまで
(1,7,11,13,17,19,23,29)+30*n
の数に対してチェックしていく
それを永遠に繰り返していくかんじ
速さは調べてないけど
テーブル自動化を目指した
途中まで(100ぐらい)しか見てないから
正しいと思うが間違ってたらスマソ
一億やるのに13秒(Pen4 1.7G・出力なし)
ただバグがあって、でかい数(2^32 -1)までやるとうまくできない?とか・・

ふるいは使ってないので誰かふるいを組み合わせて試してほしいです。
ちなみに自分はCがだめだめな学生なんで、ついでに誰かCで試して。w
563アフォ学生 ◆ZrbomZ0t3. :02/12/16 22:02
誰もレスくれないのかYO!
さびしいよ〜〜

さびしいからトリップ付けましたw
もしかして激しくガイシュツ?
そいつはスマソ
564548==556:02/12/17 00:47
>>548で>分からないと言いつつも分かったかも…
と言いつつ分かってなかったです(Pascal読めんのよ…)

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

と言うか、ここで毎回圧縮する意味は、殆どありません
2^64のような大きな値までを篩う事を考慮し
メモリ上に今までの結果を残したい場合は
0〜m1の素数を普通に篩い、その結果を元に圧縮しながら0'〜m1'に保存
m1〜m2の素数を普通に篩い、その結果を元に圧縮しながらm1'〜m2'に保存

mn〜2^32の素数を普通に篩い、その結果を元に圧縮しながらmn'〜2^32'に保存
のように、分割した方が、篩いも圧縮も早くなります
(もちろん分割した事によるロスも馬鹿には出来ませんが)
と言う訳で、長くなりましたが、頑張って下さい
自動化でたね・・・
しかも早いし
削除依頼が出てたw

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


54 名前:削除屋つまようじ ★ 投稿日:02/12/16 20:33 ID:???
>53 縦読みしつつ流してください
567デフォルトの名無しさん:02/12/17 20:36
よくわからんタイミングで削除依頼が出てるな
>>565
一億やるのに13秒で早いだと?
これが、こんなに遅いのはjavaを使ってるからでも無ければ
テーブルを自動化したからでも無い
chkSosuu()で、除算で素数判定してるからだ
もう少しコードを読んでから、早い遅いを語ってくれ
喧嘩腰になるなってば
570568:02/12/18 06:32
>>569
スマソ
571デフォルトの名無しさん:02/12/18 22:39
C++で324のコードを走らせる場合、必要なヘッダファイルは何かいな?
あほな質問でごめんちゃい。
>>571
#include <stdio.h>
#include <stdlib.h>
#include <malloc..h>
多分。
573571:02/12/18 23:02
>>572
stdbilを読み込めないと言ってくる・・・泣
>他の人
スレ違いでごめん。
574571:02/12/18 23:06
またごめん・・・
573は無視して・・・。
stdbil

なんだそれは食い物か
世界標準ビルゲイシだろ!まったくM$オタクのくせしてそんなことにも気づかない(ry
保守
ネタないですね。
AthlonXP 1800 で、やっと426 に勝ったと思ったら
Pentium2 400MHz では全然負けてました。
426と比較すると
Athlonで 11秒 と 12秒 (ほとんど変わらない)
Pentiumで 1分23秒 と 55秒 くらいでした。
http://tool-ya.ddo.jp/2ch/trash-box/file/20021222173653053.c
>>578
頑張りましたね…
でも、出来れば少しだけでもコメントをつけるなり
影響の少ない範囲で、main()のコードを複数の関数に分割して欲しかった…
力業って言葉がよく似合うコードだと思った。
581578:02/12/23 12:01
>>579 >>580
そうですね。少しでも速くすることを考えてました。
分割したエラトステネスの篩で3、5、7の倍数を省いています。
√n未満の素数(p)の場合は
((n-1+p)/p)*p
√n以上√m以下の素数(p)の場合は
p*p
から篩っています。すごく普通のエラトステネスの篩です。
滅茶苦茶汚たないのは、331に書いてあるデジタル微分解析法とやらで、計算量を減らしているからです。
こんなあほなことするより、真面目にアルゴリズムを考えたほうがいいですね。
582578:02/12/23 17:36
3、5、7 じゃなくて 2、3、5 でした。
>>581
素数の列挙の場合、マジメにアルゴリズムといってもフルイの範疇でしかないから
その手のあほな手法をチマチマくみたてあげるしか無いんだよね
584578:02/12/25 18:11
578のビットの数え方を変えたら、AthlonXP1800で8秒台に縮まりました
(ファイル出力ありの場合は変わりませんが)。
そして、set_bitのレベルにまでデジタル微分解析法を適用したら0.4秒ほど縮まりました
(そのせいでコードの長さが3900行を超えたのに、効果が少なくて悲しかったです)。
最終的に AthlonXP1800で8秒ジャスト、Pentium2 400MHzで59秒くらいになりました。
改良の余地が無いとは言えないのですが、そろそろ限界です。なのに426に勝てない。
>>583
素数公式ページみたいな所のリンクのプログラムの篩いの所に一つだけエラトステネス
でないものがあるのですが、あれはどうなんでしょう?
ある素数(p)が二つの平方数の和で表わすことができることが、 p = 1 (mod 4)と同値である(2は例外)ことを
利用しているようなのですが、そういう方法もあるみたいですね。
へえ・・・
 2*2+3*3 = 4+9 = 13 13 mod 4= 1
 2*2+5*5 = 4+25 = 29 29 mod 4= 1
 2*2+7*7 = 4+49 = 53 53 mod 4= 1

ホントだ
586 ◆2ZUH6PwhYk :02/12/28 13:42
>>540
激しく亀レスだけど

 Σ(゚д゚lll)ガーン

そのうち見直して修正しまつ。
switch で二回場合分けするより、二次元配列から値を取り出した方が
速いかなあと思ったのですが、逆に遅くなりました。そういうものなのでしょうか。
あと、分割した篩を埋めていって、はみ出た時に場所とタイミングを記憶しておけば、
全く割り算を使わずに済むかなあと思いました。
あと、良く知らないのですが、Mathematica とかいうのがくそ速いらしいですね。
素数マップを作る為にキャッシュに収まらないサイズの
メモリアクセスを行ってるから、配列を使うとそれだけ
キャッシュミスが増えるって事じゃないのかな

割算そのものは重いといっても加算減算とは別に平行して実行されるから
頻度にさえ気をつければ、除算を使ってシンプルになるなら使った方がいい。
>>588
篩のサイズをかなり小さくしたら、二次元配列のほうが速くなりました。
でも、二次元配列のサイズに比べてかなり小さくしないといけなかったので、なにか違うような。
メモリをたくさん使っているときは、配列から値を取り出す動作そのものが遅いと考えれば、辻褄があうのかな。
割り算の頻度は結構高いのですが、配列から値を取り出す動作が遅いとなると、計算したほうが速いのかもしれません。
>>589
多段パイプラインなCPUの場合、例えば割り算の
結果が得られるまでに5クロックほど掛かるなら、その間に
別の1クロックで済む命令を4個実行させられたりする。
「奴からメールの返事がくるまで暫く掛かるから、その間に
別の奴へのメールも書いておこう」みたいなのと同じこと。
待ち時間の高そうな結果依存部分が集中しないようしてやれば、あとは
コンパイラやCPU自身が判断して真の命令実行順序を考えてくれると思う…。

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

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

みたいな?意義低そうだが。
(i を register int 宣言したら効果的?)
>>590
なるほど。そういうことも考えながら書くといいんですね。
エラトステネスというアルゴリズムは工夫する余地があまりないので、
プログラミングテクニックを追及していくしかないですね。
割り算なしで一から書き直してみたのですが、やはり少し遅くなりました(書きかたが悪いのかもしれませんが)。
その代り大きな数を扱わないので、10^11くらいまでなら計算できるようになりました。
10^10まで450052511個を数えるのに
AthlonXP1800 で 21秒
Pentium2 400MHz で 4分5秒
10^11まで4118054813個を数えるのに
AthlonXP1800 で 4分20秒
Pentium2 400MHz で 45分52秒
くらいでした。
Pentium2のほうではメモリのサイズを減らせばもっと速くなると思うのですが、
メモリのサイズを減らすと計算結果がおかしくなるというバグがあるので今は無理でした。
double型を使えばもっと大きな数まで計算できると思います。
592591:03/01/01 23:34
今気付いたんですが、584に書いたdjb氏のやつは滅茶苦茶速いですね。
ファイル出力無しで比較したかったので、
primes 9999999900 10000000000 とかしてみたのですが、一瞬でした。
範囲が狭いときは篩を作らずに一つ一つ素数判定しているのならば納得できるのですが。
結局、
time (primes 0 4294967291 > prime.dat)
で比較してみたのですが、自分のより3倍ほど速かったです。
ファイル出力部分は作り込んでないので、その差もあるかもしれませんが。
とりあえずソース読んでみます。
>>592
がんがってくだちい。自分は>>590を試してみようと思ふ
594デフォルトの名無しさん:03/01/02 20:26
すまんが、>>578のリンク先からアクセス拒否をくらうんだけど。。
>>594
会員専用?
596デフォルトの名無しさん:03/01/02 20:57
で、結局何桁までもとまったの?
割り算使わないバージョンがそれなりに形になったのでアップします。
細かいミスがたくさんあって全て直したつもりなのですが、少し自信がありません。
なにかおかしいところがあったら、教えてくれるとありがたいです。
引数以下の素数の数を出力します。引数は30で割って桁溢れしない数にしてください。
速さにはあまり期待しないでください(そんなに遅くないと思いますが)。
http://tool-ya.ddo.jp/2ch/trash-box/file/20030102235159180.c
598597:03/01/03 17:14
http://tool-ya.ddo.jp/2ch/trash-box/file/20030103165147234.c
上のとほとんど同じで申しわけないのですが、出力部分を作ってみました。
-pオプションで標準出力に素数を出力します。djb氏のと近いものにしました。
そして比較してみました(AthlonXP1800メモリ512M)。
time ./a.out -p 10000000000 > /dev/null
time ./primes 1 10000000000 > /dev/null
上が1分36秒、下が1分26秒でした。
もう一桁上で比較すると、僕のが15分49秒、djb氏のが21分5秒でした。
もっと大きい数を扱うという課題はあるのですが、とりあえず速度は問題ないのかなあ。
僕は人のコードを読む能力や根気が欠如しているのでdjb氏や426のコードがどんなアルゴリズムなのか
さっぱり分かりませんでした。
今のところ、4*10^22くらいまでの素数は見つかっているみたいですね。果てしない。
ちょびっと横道にそれるのですが、
1Gh 256Mb で1時間かけてあるふたつの素数の積を
素因数分解をする場合には何桁の素因数分解ができれば優秀なプログラムと言えるのでしょうか?
>>599
普通に素因数分解をすれば、

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

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

だから だいたい64bitが素因数分解出来れば非常に優秀
600さんレスサンクスです
64bitですかぁ 簡単にはいきそうにないっす。
気長にちびちびとやっていきます。
完成すればうpするのでまっててちょ。
602597:03/01/04 13:17
double型を使って、1兆まで計算させてみたところ、1時間9分かかりました。
その間普通にパソコン使っていたので正確には分かりませんが。
一晩かけて10兆まで計算させようとしたのですが、2時間くらいで終ってしまって
答えも合っていませんでした(たぶん格上げ関連のミスだと思います)。
あと、 long long intという型があるのを知ったのですが、これは使ってもよいのでしょうか。
移植性も考えるとdoubleを使ったほうがいいのでしょうか。ビット演算もできるので少し驚きました。
素数計算の実行時間が書いてあるページがありました。ぴんとこないけどかなり速そうですね。
今から計算しはじめるのと、少し待ってもっといいCPUができてから計算するのと、どっちが速いのかなあと思いました。
http://numbers.computation.free.fr/Constants/Primes/Pix/results.html
603デフォルトの名無しさん:03/01/04 21:54
話が小さくなって申し訳ないですけど・・・。
VB6.0で組んでいるんですが、100万までだと「個数勘定なし・出力なし・
2や3の倍数をあらかじめ消しておくというのも無し」で、平均0.21秒台です。
VB6.0だとこれが限界かなぁ。。。
みなさんはどうです?
604603:03/01/04 21:56
追加

「API関数も使わない」で、です。
>>603-604
環境示せ。過去ログにVBの事も出てたよ。
606603:03/01/04 22:03
Pentium(r)V processor GenuineIntel ~800Mhz

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

ちなみに>>441のリンク先のものよりも速いですが・・・オイラのPCだと。
ん?>>441のは出力ありだろ?
>>607
ボタンをチェックすれば出力無しに出来るよ。
>>608
それでもTEMPフォルダに出力してるようだが
610603:03/01/04 22:32
>>609
本当だ・・・ビックリ・・・・。
もっと修行せねば。
ありがとう!
>>610
がんがってね。応援するよ
612デフォルトの名無しさん:03/01/05 18:46
しょうも無い話だけど、、、>>441の素数列挙アプリは
他のアプリを全て終了してから、出力無しで「2^31-1」まで
計算させようとするとおれのPCではメモリ不足のエラーが出る。
そういうことを考えると・・・・恐らく2,3の倍数を初めから
消しているのかな?
613597:03/01/06 12:38
10兆まで計算するのにAthlonXP1800で21時間もかかった...
4*10^22まで求まってるのは素数の個数で、素数表が完成しているのは10^17くらいまでみたいですね。
http://numbers.computation.free.fr/Constants/Primes/pixtable.html
ここに素数の個数を数え上げた年代が書いてあります。
1985年には分散コンピューティングも無いだろうし、スーパーコンピュータを使っているんでしょうか。
当時のスーパーコンピュータの性能はどれくらいなんでしょうか。4*10^16まで求まる気がしません。
>>597
djb氏って、それって何処にあるの?
616pascal:03/01/07 10:53
とりあえず昔同じことやったファイルがCD-Rにあった。計1G。
2^31 未満の素数の全リスト。
適当に作ったやつだから2日くらいかかったけど。(Pen!!! 1.00GHz)

使った方法は、既出だけど
1.sqrt(2^31)未満の素数リストをふるいで作る
2.それを読み込んで、新たな数nをaqrt(n)未満の素数で割る

ソース発掘中・・・。

#それとは別に10万個ずつ素数を見つけてファイルに書き込むものもあり。
#ともに暇ならUPしますが。
>>615
http://cr.yp.to/djb.html
ここの primegen ってとこです。
>>616
うpきぼーん
619pascal:03/01/07 13:57
>>618
発掘・実行してみたらとてつもなく遅かったので自主規制です(^-^;
てか恥ずかしくて見せられん。
ふるいも使わずビット演算とかもせず、ゆえに割り算ばっかりしてるので1000万までで10秒弱かかります。。。
似たことやってる人がいてちょっとほっとしました(^-^)

意味のない数値計算はよくやるので、自鯖があったらいろいろUPしたいのだけど。
円周率120億桁とか(ぉ
拾いものです。正しいのかどうか比較対象がないのが痛いけど。

駄文+横道+長レスすまそ。
そもそも円周率とは何か?
3.14
というのは円周率の定義でないと最近おもいつきはじめている。
http://tool-ya.ddo.jp/2ch/trash-box/file/20030108102710423.c
一兆まで AthlonXP1800 で56分、Pentium2 400MHz で9時間弱
十兆まで AthlonXP1800 で17時間くらいです。
-u オプションで篩の大きさを指定できます。
long long int型を使っていますが、double型で代用することもできます。
floorのためにmath.hをインクルードしないといけないと思いますが。
一応説明すると、ほとんど428と同じです。
5の倍数を省いて、もう一段階デジタル解析微分法をして、分割しているだけです。
デジタル微分解析法のところで、φ(2*3*5) = 8 が1バイトのビット数と等しいことを
利用しています(φはオイラー関数)。
428はメモリ一発だからこそできると思っていたのですが、はみ出たときにはみ出かたを記憶
しておくという原始的な方法で解決しました。
アルゴリズムがシンプルなだけに、あまり改良する余地がないです。
メモリ節約することと、set_bitでいっぱいif使ってるのをどうにかするくらいでしょうか。
僕にはあまりアイデアが無いので、これで一応終りにします。
単純なエラトステネスではここら辺が限界な気がします。だいたいみんな単純なエラトステネス
っぽいですが、djb氏のは謎なのでそこに希望があるかもしれません。
622615:03/01/08 17:05
>>597
サンスクコ
コンパイル出来ませんが
そのうち、コードだけ読んでみます
623デフォルトの名無しさん:03/01/08 19:28
>>620
頭大丈夫?
624621:03/01/08 20:18
print_primeの引数はuint64の間違いです。
だから速かったみたいです。djb氏のとは比較にならないくらい遅いです。
32ビットの範囲でも long int と long long int では割り算の速さが全然違いますね。
625620:03/01/08 23:16
>>623
円周率の定義教えてよマジで
>>625
小学校で習わなかったの?
217 名前:ひろゆき ◆3SHRUNYAXA [] 投稿日:03/01/08 17:49 ID:rLfxQ17l
   一定期間でログは消しますです。

249 名前:ひろゆき ◆3SHRUNYAXA [] 投稿日:03/01/08 17:52 ID:rLfxQ17l
   >荒らしとか犯罪のためなの?
   そす。

246 名前:心得をよく読みましょう[] 投稿日:03/01/08 17:52 ID:BH998yxV
   >ひろゆき
   俺のお気に入りのスレとか荒されてるんだがそういうのにも有効?

257 名前:ひろゆき ◆3SHRUNYAXA [] 投稿日:03/01/08 17:53 ID:rLfxQ17l
   >>246
   いずれは。
2ちゃんねる が衰退していく

あるネット関連会社の社長は、
「いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう」
と証言する。
2ちゃんねるが判決によって力を失った場合、
資金提供の打ち切りも予想される。

http://ascii24.com/news/reading/causebooks/2002/07/01/636911-000.html
>>625
円の面積÷半径の2乗
節穴ないスレは落書き>無視
節穴はマジ書き>通報
ってルール駄目?

警察忙しくなりそうだな。
631デフォルトの名無しさん:03/01/09 14:48
いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう
632625:03/01/09 16:03
>>626
小のころは遊んでばっかりで、勉強しなかったから。
>>629
S=πr^2

π=S/r^2
に変形してもいまいちπの正体が見えないな。
「円周を直径で割った数」でいいじゃん

つーか検索しろよ
======2==C==H======================================================

         2ちゃんねるのお勧めな話題と
     ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数: 138720人 発行日:2003/1/9

年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。

そんなわけで、年末に予告したIP記録ですが実験を開始しています。

「2ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。

んじゃ!

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
>>633
それが算数の授業での説明なわけね。
2chねらーに聞きたかったんだよう。
>>635
半径1の円を内接、外接する3角形で近似する。
極限をとれば、同じ値に収束して、その値が円周率。
>>635 「円周率って何?」と聞かれたら、やっぱり定義を答えるだろう。2ちゃんねらーでも。
だったら>>633が正解。

ム板的に、円周率の近似計算アルゴリズムを聞きたいなら別だけど。
>>743 盛り上がるのは結構だが、pc系の荒らしにはもう疲れましたよ(;´Д`)


個人的にはエロっぽいギャグも誹謗中傷ととられたら俺もIP記録はやばいな(;´Д`)
OK.

録音とか(盗聴も)
してていいです。
只、そのノイズも国家機関に分析されます。

2分後に掛けます。
自己紹介と、一般の世間話をしたいと思います。
最初に確認したいのですが(深夜で遅いし。用件もあっさり、こってり。一見だし)
「私」青少年が色々と危機的なんです。

「早急に」+、前向きに
色々と検討して下さいますでしょうか。
私は18歳です。其方のプロフィールを簡単に今お願いします!ありがとう。
んじゃ俺今からけんすうにワン切りしよ(^_^;)
ついさっきNHKFMの2時のニュースで2ちゃんのこと言ってたぞ。
誹謗中傷と認識 ← ここの基準をしっかりしなくてはならない。
          削除人の個人個人の判断じゃだめ。
他が危険で、にちゃんも危険になったとでも〜
の間違いだと思われ。
IP取ってない方が珍しいし。
644デフォルトの名無しさん:03/01/10 12:15
すれ違いサぁ
ヾ( ゚д゚)ノ゛シナチクー
某、毒見要員だったのでござるか|/゚U゚|

小1時間経ちましたがまだ腹痛は来てないので大丈夫そうです。
あずき缶と白味噌、里芋を買って正月に備えます。ビバ独り身。
大阪キタ━━━━━━(゚∀゚)━━━━━━ !!!!!



注意:ここは素数列挙アルゴリズムスレです
2003年1月10日がおいらの青春の1ページに記録されますた。
なんかこれ見よがしに必死に他の掲示板へ誘導してる香具師が居るように見えるんだがw
えっと、無知で突っ込みを入れられるのを覚悟で。。

IPの記録が抑止にもなるなら、削除系の板のリモホ表示をやめて
みるのはどうでしょう。
依頼者のホストを削除板以外の板に晒されることもないでしょうし。
「氏ね」だとかはいいよね?
管理人は「逝ってよし」もダメだと言うのか!?
P2P専用掲示板zigmoを再開発していると作者が言っているが。。。
======2==C==H======================================================

         2ちゃんねるのお勧めな話題と
     ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数: 139038人 発行日:2003/1/10

なにやら、連日メルマガだしてるひろゆきです。

そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。

重くなって落ちたりしてもご愛嬌ってことで。。。

んじゃ!

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
ちくり板つまらなくなりそなヨカン
無線LANでNYBBSをやるのが好ましいのでしょうか?
内部告発やったら自分がただですむわけナイヨ
659デフォルトの名無しさん:03/01/11 12:50
>658
復讐的なチクリもなくなるのだぞ!!
何が実験だよ
IPなんか始めから記録してるだろよ
逆に立てて欲しくなかったんだが(w
半角板がおもしろい
2chで告知するかどうかを知ることで?(^_^;)なんでそうなるんだ?

そりゃそうだ(^_^;)まあハッキングと強盗は区別するってことで

20レス分くらい読めよ(^_^;)

どこまでOKなのかわかってたら訴訟で負けたりしません(^_^;)

なるほど(^_^;)
あきらめる(・∀・)
中部地区では一週遅れで今の時間にやってる。でも悔しくないのが種の良いところだな
>>665
誤爆?
少女漫画かアニメ板から
祭り開催中!!!
メンヘルと言ってた女が実はシャブ中だった!!!
http://tmp.2ch.net/test/read.cgi/tubo/1042129878/l50
博之は寝た。
やっぱりな・・・・
>スパーハカーにIPから本人のメアドを割り出してもらう
Hackerの名を汚すな。馬鹿。
IPからメールアドレスだと?
馬鹿か。割り出せるのは契約者の接続アカウントだ
書き込めた!  倉庫板さんオツ!感謝!
672 :03/01/13 18:24
test
673山崎渉:03/01/13 18:43
(^^)
つまんね
675山崎渉:03/01/15 17:50
(^^)
676山崎渉:03/01/23 22:23
(^^)
677デフォルトの名無しさん:03/01/27 00:04
何で荒れてるんだ???
ごめん、関数と方程式間違えた。。。
679デフォルトの名無しさん:03/01/30 23:41
ねー
巨大素数の計算式もうできたんでしょ>?
680デフォルトの名無しさん:03/01/31 01:18
予め2と3と5と7と11と13と17の(以下略
>>679
ロシアの数学者が何十年も前に考案しています。
素数x素数+1
>>682
がどうした?
684デフォルトの名無しさん:03/02/02 22:54
おれが最速のやつをつくるまで消えないようにあげ。。。
685デフォルトの名無しさん:03/02/11 09:47
はじめてCで素数のプログラム作ったよ。
$ date ; ./a >prime1oku.dat ;date
Tue Feb 11 09:12:05 2003
Tue Feb 11 09:13:43 2003
1分40秒で1億までいけますた。
Pen2 350Mhz でcygwin gccです。
686デフォルトの名無しさん:03/02/16 16:41
保守浮上
tes
688デフォルトの名無しさん:03/02/19 01:31
>>688
>N以下の素数の個数を示すのに、Nまでの数字を全部チェックする
>バカはいないだろ。
>(ルートNまでという意味ではない)
なんで、これで素数定理が出てくんの?
求めたいのは、およその個数ではなくて、正確な数でしょう?
およその数で良いのなら、最初から、そう書いてけよ
それとも、これで正確な数が出るとでも思ってるの?
690デフォルトの名無しさん:03/02/19 02:51
ルートNまでの素数で割り切れないNをどんどん探していく。
それより早いアルゴリズムはないんじゃない?
691 ◆8/MtyDeTiY :03/02/21 15:25
>>690
Nまでの数をふるいにかけて、
数え上げたほうがはやそう。
692デフォルトの名無しさん:03/03/03 18:49
浮上
693621:03/03/03 19:04
ネタないですねえ。
古い話ですが 621 の print_prime を書き直したら4000億あたりから621のほうが
djb氏のより速くなりました。しかし速いといっても微妙なのでなんとも言えません。
Pentium2 400MHz では621のほうが全然速いので環境によって結構変ってくるみたいです。
で、数論の入門書を見ていたら面白そうなことが書いてあったので引用してみます。
694621:03/03/03 19:08
「数論入門I 」より引用します。

n番目の素数 Pn の単純な一般式はあるか? (すなわち、与えられた
nに対してエラトステネスのふるいよりも楽に Pn の値を計算できる公式が
あるか?)
そのような公式は知られていないし、そのような公式はありそうもない。
一方、様々な Pn の「公式」を考案することはできる。これらのうち、あ
るものは Pn をそれ自身を用いて定義しており、従来知られていない Pn の
値を計算することができないので、ほんの興味をそそるものにすぎない。定
理 419 において例を与える。他のものは理論的には Pn を計算することがで
きるが、エラトステネスのふるいよりも実質的に多くの労力を払うことによっ
てのみ可能である。 その他のものはエラトステネスのふるいとなお本質的に
同等である。

要はエラトステネスが最良のアルゴリズムであるということが証明されてるみたいです。
695デフォルトの名無しさん:03/03/03 19:53
>>621のソース読もうと思ったら、アクセス拒否された。
もう消えてる? それともYBBだから?
696デフォルトの名無しさん:03/03/03 20:27
>>695
保存できない?
>>688のリンク先に載ってる多項式n^2+n+41については
数学板にスレが立ってますよん
http://science.2ch.net/test/read.cgi/math/1006151996/-100
>>694
> 「数論入門I 」より引用します。
これって誰の本?
699621:03/03/03 21:38
>>695
もう消えています。アップローダーだといつかは消えてしまうのでしょうがないです。
>>698
G.Hハーディ/E.Mライト 著
示野 信一/矢神 毅 訳 です。結構古い本です。
プログラム板的には「はじめての数論」も良いと思います。
プログラムを書く問題があったり、暗号についての話があったりします。
ただ証明は大体「数論入門I」のほうが分りやすかったです。
700695:03/03/04 08:29
>>699
よく見たら、日付が1/8でした。
番号がそんなに違わないし、同じ話題が続いてるので、
少し前の公開かとカン違いしてました。
保守
保守
まだ改良頑張ってる人っている?
( ´∀`)ノ
>>704 癌がれ。
じゃあ、当分は定期的に保守しておくよ。できれば途中経過など聞かせておくれ。
706デフォルトの名無しさん:03/04/10 00:31
ウーン頑張ってもどうしても1億で1分4秒@pen2-350 Cygwinが限度でつ
707706:03/04/10 03:03
http://members.tripod.co.jp/firstbornunicorn/prime.c
ダメだMAXが10^10を超えるあたりからcallocができないっす。
よってやめます。
メモリをケチることは重要っぽいです
1億くらいまでは正しく求められそうでした。

stdout だと遅いかと思われるのでリダイレクトして

#define MAX ???
に求めたい素数列の最大の値をいれてください
http://mathquest.com/discuss/sci.math/a/t/437162
ここに書いてあること分かる人いますか?
僕は英語苦手なのでよく分かんないんですけど、かなりレヴェル高い気がします。
あとdjb氏のより速いプログラム見つけた人いますか?
最近 primespeed で個数だけ数えてくれることに気づきました。
709山崎渉:03/04/17 15:33
(^^)
http://www.google.co.jp/search?q=cache:lCAiHroWRnkC:mathforprofit.blogspot.com/+&hl=ja&ie=UTF-8
一応キャッシュ消えないうちに貼っときます。
とんでもなく速いですね。JAVAなのに。
http://ourworld.compuserve.com/homepages/hlifchitz/Homepage.htm
エラトステネスの計算量は O(n*log(n)) らしいのですが、O(n^(1/2)*log(n))
で計算できるらしいです。dvi ファイルに詳しく書いてあります(僕は理解して
いませんが)。
>>694 との関連はよく分りませぬ。
712711:03/04/18 19:47
アドレス微妙に間違った。
Parity of pi(n) ってとこです。
nまでの素数を篩うんだったら、√nまでの素数を元にすればよくて、
これがループ回数を決定するから計算量はこの素数たちの個数で求まる。
で、素数定理よりその素数たちの個数が1/2 * n^(1/2) * log(n)個程度だから、

……でいいのかな?
>>713
今適当に考えてみたのですが単純にステップ数を数えると、
p <= √n 、 Σn/p ですよね。
Σ1/p <= log(√n) だから
O(n*log(n)) になるんじゃないのかな。
715713:03/04/20 00:27
あ゛っ。そんな気がしてきた。
とりあえず>>711のソースを読んでみまつ。
http://seizen.gikoneko.net/~2ch/prime/
作ってみました。
ソース改良したり、アップしたり、リンク足したり、なにやってもよいと思いますが
いつ消えるか分りませんのでご注意。
717711:03/04/28 10:05
>>711
の O(n^(1/2)*log(n)) で計算できるのは pi(n) の偶奇 ppi(n) らしいです。
ppi(n) + ppn(n-1) で n の素数性が分るみたいです。
一つの数の素数判定に O(n^(1/2)*log(n)) かかるので pi(n) を求めるには
O(n^(3/2)*log(n)) かかり、エラトステネスより効率悪いみたいですね。
保守。
719山崎渉:03/05/28 13:25
     ∧_∧
ピュ.ー (  ^^ ) <これからも僕を応援して下さいね(^^)。
  =〔~∪ ̄ ̄〕
  = ◎――◎                      山崎渉
保守アゲ
(盛り上げていこうぜ!!山崎渉なんかに負けんな〜)
721デフォルトの名無しさん:03/06/15 14:18
パソコン買い換えて環境早くなったもんだから多少いじっても何も変わらん…
722デフォルトの名無しさん:03/07/06 23:37
プッチ神父のスレはここですか?
723山崎 渉:03/07/15 10:06

 __∧_∧_
 |(  ^^ )| <寝るぽ(^^)
 |\⌒⌒⌒\
 \ |⌒⌒⌒~|         山崎渉
   ~ ̄ ̄ ̄ ̄
724磯引葦胃葦斡:03/07/17 18:48
磯引葦胃葦斡
>>722
すっかり落ち着いてますが
726山崎 渉:03/08/02 02:56
(^^)
よく分からんけど、とりあえず貼り
http://www.msnusers.com/AmateurMath/primecountingfunction.msnw
ちなみに PrimeCountH.java はくそ速いです。
今までの苦労はなんだったんだ ってくらい。
729山崎 渉:03/08/15 18:05
    (⌒V⌒)
   │ ^ ^ │<これからも僕を応援して下さいね(^^)。
  ⊂|    |つ
   (_)(_)                      山崎パン
730デフォルトの名無しさん:03/08/20 18:09
静岡、想い出登板キタ━━━━━━(゚∀゚)━━━━━━ !!!!!
n^p/p=x…n
n…適当な数 p…素数 
保守
保守
734デフォルトの名無しさん:03/09/17 19:25
C++初心者ですが、この素数判定アルゴリズムはやはり低レベルでしょうか?

template<class T>
bool primality_test_1(T mainvalue)
{
//偶数を判別(奇素数判定ならこの部分はいらない)
if(mainvalue % 2 == 0 || mainvalue == 1)
return mainvalue == 2 ? true : false;
//事前条件: mainvalueは奇数 && mainvalue >= 3
T i = 3;
for(; mainvalue % i != 0; i += 2)
;
return i == mainvalue ? true : false;
}

mainvalueの平方根をとればもっと速さを短縮出来ると思ったのですが、
それをやると、第2forループの「番兵」が活かせなくなってしまうので、
何かよい方法はないかと思案しています
735 :03/09/17 20:11
↑良い悪いはともかくとして、これより低レベルなアルゴリズムってあるかな?
>>735
偶数も含めて除算していくアルゴリズムが在るだろw


そろそろエラトステネスについては語りつくしたようだしテーマを変えてみないか?

次のテーマ "エラストテネスの篩い以外のアルゴリズムでどれだけ速くできるか?"

まずはウィルソンの定理あたりでw
判定スレ落ちてるので、こちらに書きます。

判定用アルゴリズムで、こういうの考えました。
多分速くは無いけど、メモリはそんなに使わないと思います。
2〜7の素数はデフォルトとして桁数が多い場合の処理を考えてみました。

たとえば8137の場合
もしこの数が素数でなければ、下1桁が1×7、または3×9の数字の積だと言うことがわかる。

そこで(1×7の計算は終わった物とします)
  ___9
 3) 8137
      27
    811
3と掛けて下一桁が1になるのは7だから

  ___79
 3) 8137
     237
    79
3と掛けて下一桁が9になるのは3だから

  ____379
 3) 8137
    1137
    7
3と掛けて下一桁が7になるのは9だけど、3×9379はもとの数より大きいのでスキップ

つづく
つづき

  ______9
13) 8137
     117
    802
と言う感じに計算すると、

   ___79
103) 8137
     8137

となり、素数ではないことが分かる。
こんな感じで計算すれば、桁数が多くても網羅する範囲を絞れないでしょうか?
>>737 質問です
13,103はどうやって決定するんですか?
13,23,33,43,53… って10の位を増やして全て計算するんですか?
除算のみを使った列挙で1000万まで7秒ってどうですか?
(篩いなら一瞬だろうけど)
どんな環境で?
地球シミュレータ上で
   / ̄ ̄ ̄ ̄ ̄ ミ
  /   ,――――-ミ
 /  /  /   \ |
 |  /   ,(・) (・) |
  (6       つ  |
  |      ___  |   / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
  |      /__/ /  < なわけねぇだろ!
/|         /\   \__________
n = (x * x + x + 1) / 4
sqrtを使わずにxについて解く事って出来ますか?
>>744
ニュートン法などによる近似
x^2 * 2 + x * 40 + 1
x^2 * 2 + x * 44 + 43
x^x * 2 + x * 48 + 89
>>739
レスきてた。

やっぱりそこですよね・・・。
それなら、判別する数の下一桁が1,3,7,9の場合、下1桁が1,3,7,9の数で順番に割ってみるっていう風にしたほうが早いですよね。

下一桁が0,2,4,6,8の場合は偶数、下一桁が5の場合は5の倍数なので判別する数が2桁以上の場合、必ず素数にはならないのですぐ結論が出るし。

下一桁が1の場合素数でなければ下一桁が1×1、3×7、9×9の合成数
下一桁が3の場合 〃 1×3、7×9 〃 
下一桁が7の場合 〃 1×7、3×9 〃 
下一桁が9の場合 〃 1×9、3×3、7×7 〃 

これをどうにか利用できないかなぁ・・・
>>747
とりあえず二進法で考えて下さい。
割り算がしたいのなら多倍長計算スレへ。
749デフォルトの名無しさん:03/10/02 02:00
篩を使い、偶数のみ除いて
300万で30秒まで行きました。
まだまだ未熟者です。

リンクのソースを読もうと思ったら、
ほとんどリンク切れしてしまっていたのですが、
誰か早いのを作っている方で、
もう一度リンクを張っていただけないでしょうか?
できればCでお願いします。
>>426
>>617
>>727 はどっかいったみたい。ソース持ってるけど。
integer n > 1
 1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;
 2. r = 2;
 3. while(r < n) {
 4.   if ( gcd(n,r) != 1 ) output COMPOSITE;
 5.   if (r is prime)
 6.     let q be the largest prime factor of r - 1;
 7.     if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1(mod r) )
 8.        break;
 9.   r = r + 1;
 10. }
 11. for a=1 to 2*aqrt(r)*log(n)
 12.   if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n) ) output COMPOSITE;
 13. output PRIME;

これって結局何だったの?
PrimeCountH はエラトステネスではないようなのですが誰か解説きぼん。
753デフォルトの名無しさん:03/10/04 14:44
>>750
ありがとうございます
754わむて ◆wamuteW7DE :03/10/04 15:07
             _
  (      .,‐ '´   ヽ-、_
       /⌒)i レノノ))) \ヾヽ   / ̄ ̄ ̄ ̄
     /ヽ './人il.゚ - ゚ノイ|/.ヾヾヽ<  みる、みる、みるまらーーー!
 ゞ   ("....( (ヽ ⊂)Yiつヽ) |'ノ    |  わむてさん、地球!
     (" "ヽ\.' く _ :|〉ヽ.ヽ| | ノ  |
        '( " ヽ\し'ノ  ヽ| |ノ  ノ   \____
   (\     '("ヽ\     |ノ
   \)       '((.     "   し″
「4以上の全ての偶数は2つの素数の和であらわせる」
言数μの儀環δ(μ)によって外数μ'/偶数は定位を持つ。(自明)
線形乖離により轍環はδによる写像σの約値を持つ。
轍環は無限順列を持たない為、輪位は定位と双対ではない。(μ'までも乖離される。)
律価をοとすると言群をMとし、単置換をπとすると、約値が相似単置換π'に相当し
∀{∀(∀σ , ∃π) ,∃π' s.t δμ=φ},∃ ο∈NM s.t δπο∽σπ'μ が言える

これを展開すれば、言数定理によって、乖離され、
δπμ'=φ となる為、補遊値は0になる。
自然数においてδの域数 ω(δ)=2,
πの弄数 Å(π)=2 であり、 ω(δ)Å(π)=4
補遊値=0だから4+0=4。

∴4以上の全ての偶数は2つの素数の和で表せる
C初心者でこのスレの人たちには到底追いつけないのですが、
自分が発見した素数の定理を使用して素数列挙プログラムを作成しています。
それで、コンソールアプリケーションしか作れないのでそれでDOSに素数を表示してるのですが、
PCが計算して出した結果をDOSが表示するのに追いつきません。
このような場合は表示を省いてもいいのでしょうか?

また、計算を始めてから結果を出すまでの時間はどうやればよいのでしょうか?
よろしくお願いします。
>>756
コンソールに出さずにファイルに出せばいい
758756:03/10/19 20:58
>>757
それでやってみました
時間の問題は他人のソースをパクって解決しました。
で、結果ですが10億までの素数ならcele700で18秒でした
もっとプログラムの勉強をすれば短縮できそうです。
10億で18秒って鬼だと思うんですが
出力して18秒なら鬼
>>758
まさかと思うがラビンテストでやってないよな?
762756:03/10/20 13:18
本当に18秒台です。C言語で。
ただ、ファイルには出力せず、DOSに一部を表示してるだけですが。
もちろん表示してるのは少なくてもしっかり全部計算してます。
また、この定理をコンピューターで使用すると
今までのように素数の桁が大きければ大きいほど加速度的に計算時間が伸びるようなことはなく、
少ない桁のときより少し大きいだけで済むと思われます。

100億とかも調べたいのですが、unsigned long intでも40億程度までしか調べられないんですね・・・。
>表示してるのは少なくてもしっかり全部計算してます。
なんだよ。神が降臨したかと思ったじゃねーか。
>>762
割と最近発見された,多項式時間で素数/合成数を判定するアルゴリズムは
係数部分が馬鹿でかいと聞いたがな…
765764:03/10/20 21:17
>>762
決定的多項式時間で素数判定するAKSアルゴリズムは
桁数の12乗のオーダーだそうだ
766756:03/10/20 21:31
>>763
スマソ・・・ 表示するだけとしてはまだまだ遅いんですか?

>>764
自分はそれほど詳しくないしC言語も初心者レベルなんですけど
素数列挙って面白いですね。
AKSアルゴリズム、いつかは自分で理解できるぐらいになりたいです。
十億で18秒って早くないか?


ん・・・俺が無知なのか?
>>768
上の18秒はCeleron700なので,こっちのが速そうだ
一度全く同じ環境で試して欲しいもんだ
つーか、>>764はさっさとその定理を証明して発表汁。
そうすればもしかしたら素数アルゴリズムブームが起きるかも試練
だからさぁ、>>762は全部表示していないという時点で終了
ファイルに出力してみろってんだ
列挙型じゃないけども
p=2*3*5*7*11*13*17*19・・・ +1
素数を順番にかけていって最後に1を足せば必ずpは素数ってのを利用して
世界一大きな素数を発見ってできるかね?
これだと結構大きな素数発見できるはずだけど
素数をあらかじめ順番に大量に並べておかないといけないから前処理が大変。
目指せ100万桁ってのは無理かな、無理だね。
>>773
>素数を順番にかけていって最後に1を足せば必ずpは素数

電波は混乱のもとになるので帰ってくれ
2*3*5*7*11*13*17*19+1 = 9699691 = 347*27953


何の確証もない仮説を書き込む前に一つくらい試してみろよと言いたい
合成数を並べて階差をとっていくと・・・
━━━━━━(゚∀゚)━━━━━━・・・(´・ω・`)
>>773 >>774
なるほど初めて気づいた

確かによく考えると
「素数が無限に存在する」ことを証明するこの論法は
素数が有限という「誤った仮定」を利用して
全ての素数(実際は無限に存在するが)を掛けて 1 足すと素数…
とやっているわけだから
無限に存在する素数のうちの有限個を掛けて 1 足す
で成り立つかどうかは分からないんだよな

実際 >>774 が反例を示してくれているし
>>774
手計算ではしんどいからやらないが、
2*3*...*p+1
と 2..p の全ての素数を掛けて 1 足した数が合成数となる最小の素数 p は何?
19 より小さい p はある?
ただ、大きい素数は抽出できるが素数列挙には向かないな。
779777:03/10/29 22:00
自分でやってみた

2 * 3 * 5 * 7 * 11 * 13 + 1 = 59 * 509

13 か…人に説明するネタに使えそう
10億18秒って速くないか?
桁数が上がっても加速度的に計算量が増えないって言うし。
本当なの?
訂正。桁数が上がっても加速度的に計算量が増えないって本当?
どうでもいいから PrimeCountH を解読すれ。
783Fromごみ箱:03/11/07 14:03
$i=2;
print "$i\n";
$s='o' x $i;
$pattern="($s)*";
while(1){
 $s=$s.'o';$i++;
 #print "s=$s\n";
 if ($s!~/^$pattern$/){
  print "$i\n";
  $pattern=$pattern.'$|^('.'o' x $i.')*';
  #print "$pattern";
 }
 #getc;
}
>>783
Cygwin で実行すると 256 の壁に当たったようで
258 番目の素数として 1622 とか出力してるな
primes = 2 : sieve [3, 5..] where
        sieve (p:xs) = p : sieve[ n | n <- xs, n `mod` p /= 0]
786Fromごみ箱:03/11/07 16:41
>>784
ActivePerlでも1600超えると落ちました
正規表現が大きくなりすぎるのかも
正規表現雑技のページを見て割り算とか篩とか
使わずにやってみたくなったんだけど
シンプルじゃないうえに欠陥品でちょっとガッカリ
787ついに完成(?)世界最速:03/11/12 01:55
結局現段階で一番早いのは誰のソースですか?
できればそのソースも見たいです。

私が1ヶ月前にこのスレを発見していろんな意見を参考にして作ったのとどっちが早いか勝負してみたいです。
ファイル出力はしなくてもOK、時間表示が出ていればOK
最速ではないが、とりあえずこれと比べてみれ
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
だから PrimeCountH だっつーの。ググれ。
>>789
数えるだけじゃダメだろ
>>790
そっか、数えるだけじゃダメか。
数えるのも一個一個値出すのも一緒じゃんって思ったけど、
PrimeCountH はエラトステネスじゃないから違うのかな。
数える速さはだんとつで速いと思う。
>>791
エラトステネス使ってるだろ。
>>792
それはルートNまでの素数を計算してるだけでは?
>>793
そうだけど、それが何か?
>>794
だから核となるアルゴリズムはエラトステネスじゃないってことだよ。
あたまだいじょうぶ?
>>795
ハァ?
素数 "列挙" できるのはそこまでだろ?
スレタイちゃんと読んで出直せ。
>>796
だから >>791 の発言につながるわけですが...
どこかのスレで「参考になるループ発言」にでも使われるのだろうか。
見事すぎる。
799ついに完成(?)世界最速:03/11/12 22:45
負けました。
出直してきます。
800デフォルトの名無しさん:03/11/13 11:42
ん〜〜〜〜〜。なんか、既存のソースの検証ばっかになってない?
クリエイティブにいこうぜ!!
既存のソースの検証をせずにクリエイティブな仕事のできる天才はどこですか。
そもそも素数列挙ってアルゴリズムはエラトステネス一択だし、
素数判定や素因数分解みたいな高尚なテーマに比べるとずーっと奥が浅い。
素数カウントはそれなりに難しいのかもしれない(おれは分からない)。
pi(x) project ていうのあるしね。
解析数論の進展により,初等的ではない新しいふるい法が開発されて
素数列挙がさらに高速化するという可能性は無いのか
無いことを証明するのは難しいな
「素数定理を初等的に証明せよ」
まず素数定理とは何だ?
あれだ
ガウスが15歳の時に思いついたけどガウスにとっては初等的過ぎて証明しなかったやつ
その後誰かが手柄横取りした
初等的の意味分かってるのかと
>>806=初等的=簡単と思ってるアフォ
保守
俺はものすごいアルゴリズムを考え付いたが、
多分このスレでも既出だろうし、なにより余白が少ないので
保守だけさせてもらいます。
保守が必要だと思うなら発表してこのスレに命を吹き込んでくれ
期待はしてないよ。

既出「だろう」し、ということは「読んでません」と言ってるようなもの。
他人の意見に興味を示さない人に大したことができるとは思わない。
814デフォルトの名無しさん:04/02/05 16:47
>>813
812は、フェルマーのパロディだろ。
もう素数列挙は限界みたいなので素数カウントに興味が移り始めたのですが、
おもしろいページを発見しました。PrimeCountHなんかもこの計算方法を使ってるんでしょうね。
http://mathworld.wolfram.com/PrimeCountingFunction.html
はっきり言って、このスレはすごい。
2ちゃんねるでやるにはもったいない。
どこでやるなら良いのかと。
>>817
ドトール
819デフォルトの名無しさん:04/02/09 20:23
アスキーから出版されてるプログラミング作法、このP68の問2-4解けるかたいませんか?

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

問題の意図はおそらくO(n^2)よりも遅いソートアルゴリズムを見つけよだと思うのですが…
お知恵を貸してもらえませんか?
お願いします。
820819:04/02/09 20:24
あっ、すいません。
スレ違いでした。
無視してください。
どこらへんがすごいんだよ。
保守
823デフォルトの名無しさん:04/05/24 21:19
正直な話
素数さんと結婚するにはどうしたらいいですか?
>>823
子供を産んで、「素数」と名づけるほうが現実的。
825823:04/05/26 00:27
このスレって人いたんだな
ずっと放置かって
わびしさを感じようと思ってたんだけどな
そりゃageればな
827823:04/05/26 18:43
>>826
定期的にチェックしてるのかよ!!!
>>827
バカなの?
いやいや
>>823は確かにageたんだけどさ
>>825はageてないだろ

なのに半日もたたないうちに
>>826のレスがあったから
>>826は定期的にチェックしてるのかよ!!!
っていうレスを>>827でしたわけ
>>829
2chブラウザのスレ一覧を最終取得日時か最終書き込み日時でソートしてれば
最近レスしたスレにレスがあればすぐ見ることができるでしょ?
本人じゃないから分からんが別に定期的にチェックしてたのとは違うと思うよ。
ひまだのう
このスレ見てる椰子は
手を上げて
ノシ
(@u@ .:;)ノシ
834名無しさん@Emacs:04/06/06 14:51
ノシ
ノシ
おい、今二回手を上げたやついただろ
素因数分解してみたまへ
68228966604347
普通に割り算したらできたけど。
9333113 7310419
>>838
( ´・∀・`)へー

28347681350622442076102437227047036279370375374966
02761076051676968780023033056412274753966959194281
23826876790980636135577027355018080405658377196148
25204708757084342552431413687656764459968946860901

これはどうだ
200桁の合成数です
一行50桁となっております。
2 43 179 55213 33352217547282731980572401063704197838103
7 7 10993 271553 18876064647159886325909391381305666761
2 2 3 1433 18205739579 76108183479522373499388340361881397
246512013571 1157771962604483 88312171996847023952957
それ以上は聞かないで...
ここは暇なインターネットでつね
200桁は無理だよ。
やっぱそうですかね
どなたかRSA暗号で平文を暗号化して
公開鍵を公開してこの暗号を解いてみろとやってみてくださいな
>>843
完全にスレ違い
専用スレでも立てれば?
ただし他の(暗号解読の話題に一番適した)板で
http://primes.dnip.net/primes_1_1.tar.gz
昔作ったやつを改造してみますた。
計算量増えてるけどメモリ効率は良くなってるので、一兆くらいまで計算すると前のより早くなるはず。

10兆とか100兆までの素数すべてを記録しておくことなどできっこない。
かといってメモリ回すだけじゃ意味ないから素数の個数を出力するようにしたんだけど、
数えるだけならもっと速いアルゴリズムがある。
エラトステネスのふるいに価値があるとしたら、ある範囲(結構広め)の素数を探すとか特殊な素数(双子素数とか)を探すとか
になってくると思う。
>>845
どこのへんの人だい?
すっかりさびれちまっててすまねぇなぁ
100兆まで計算させてて320時間くらいたって、あとちょっとで計算終わりそうって時に
東京電力の検査が来ました (⊃д`)

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

昔、N以下の素数をあらかじめ省いて計算するプログラムを書こうと思って、
プログラムを書くプログラムを作って巨大な switch文を生成したことがあります。
すごくコンパイル時間がかかって、バイナリがでかくなって、ちょっとだけ速くなった
とかいう感じでした。
今なら C++で書けばすっきりしそうな気がします(相当マニアックなことしないといけませんが)。
すごくやりがいはありそうなんですが、なかなか暇がないです...
>>847
C++使えば確かにすっきりはすると思うけど、
それに伴い速度が、落ちると思うよ…
>>848
いくつかの素数の倍数を省いたエラトステネスをを素直に実装すると割り算が必要になってきます。
でもそれは、あらかじめ差分を計算しておくというテクニック(>>331)て回避できます。
素数候補の数も変わってくるので場合分けの数も変わってきます。
こういったメタプログラミングをするのに C++の templateが有効だろうと思ったんです。

でも結構大変で本当に実現できるかどうか分かりません。
あと、思ったより templateの展開が遅いです。11まで省くのは無理かもしれません。
コンパイル時にエラトステネスで素数計算させてみると、100までで7秒くらいなのに200までだと1分以上
かかったりします。
正直 templateのことはまだよくわからないです。
>>849
なるほどね
でも、実行時の速度を考えるならテンプレートを作るよりも
Cのソース(の一部)を吐き出すプログラムを作った方が速くなりそうな気がする
テンプレートって色々出来るけど、実行時の処理が重くなる時が多いので…
まぁ、使い方にもよるし、上手く使えれば、そんな事ないかも知れないけど…
>>850
その通りですね。
ソースをべたべた張りつけるような用途にTemplateは向いてないみたいです。
inline展開を信用すれば同じことができるんですけど。
とりあえず文字列レベルのマクロで十分なのでm4というのを使ってます。
クォートだらけでわけわからないですけど、まあ意図通りに展開されるのでいいかなあと。
肝心のプログラムはなかなか意図通りに動かないです。
コンパイルに10分以上かかってめんどくさいし。ほんとに速くなるのかな?
852851:04/07/14 00:36
なんとか苦労して7の倍数まで省いて計算するコードをm4で生成しました。
ソースコードは3M弱、実行コードは800Kくらいで、計算結果も正しいものに
なったのですが速度は遅くなりました。やっぱり5の倍数までがちょうどいいみたいです。

自分のより速いのも見つからない上に、たいしたテクニックを使ってないというのもあり
またエラトステネスの意義自体微妙なのでとりあえず終わりにします。
>>694 の Pnをを求めるっていうのも適当に当たりつけてカウントしてからふるった方が
速いんじゃないかって気がします。適当ですが。
853デフォルトの名無しさん:04/07/25 00:15
50桁の問題4つじゃなくて200桁の問題だろう。
何となく
age
856デフォルトの名無しさん:04/10/24 00:46:45
大地震翌日age
857デフォルトの名無しさん:04/11/12 22:33:19
個人的に良スレだから保守しておきます。

858デフォルトの名無しさん:04/11/19 02:20:16
現状(Pen4 2.4G)
1億までの列挙に 9 sec
10億までの列挙に 102 sec
列挙先はファイル

10億で18秒か…、先はなげー
859デフォルトの名無しさん:04/11/19 11:15:15
とりあえずエラトステネスのふるいのまとめ。
そんな奥の深いアルゴリズムではないのでやれることは限られてます。
1. ふるいをビットで保持
2. 小さな素数をあらかじめ省いておく(おそらく 2,3,5までが最良)
3. 2.によって生じるビットの位置を求める計算を割り算ではなく場合分けで行う
4. ふるいを分割する
僕の知ってる限りではこのくらいです。

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

1,2,3については >>428にまとまってます。あとはふるいの分割ですが、これによって
3がちょっとだけ複雑になります。
ビットカウントにHacker's Delight方式を使うなど細かいことはありますが
おおむねのアルゴリズムはこんなもんです。
860デフォルトの名無しさん:04/11/19 11:21:26
そんなエラトステネスのふるいの計算量のオーダーは O(NlogN)ですが
もっとオーダーの良いアルゴリズムがあるようです。

http://cr.yp.to/ntheory.html#primesieves
計算量のオーダーは O(N/loglogN)らしいです。
861デフォルトの名無しさん:04/11/19 20:28:21
暗号なんかで使う素数を作る時には
素数候補に対して2000以下の素数で割ると
前処理の効率が一番いいんだけどな。
862デフォルトの名無しさん:04/11/19 23:00:51
今現在で
CPU 2.0GHz
MEM 1GB

のPCを1000台使って並列処理させて
ビット数が等しい素数p,qの積n(256bit)を
素因数分解しようとしたらどれくらいの時間が掛かりますか?
863デフォルトの名無しさん:04/11/20 01:49:42
本日の状況
1億までの列挙に 5.313 sec
10億までの列挙に 56.703 sec

>>859, 860, 861
ありがと (まだコードに落とせてないのもあるけど)
864デフォルトの名無しさん:04/11/20 09:00:33
>>862
p,qの性質によるだろ。例えば、p.qが双子素数なら、一瞬で終わる罠。
865デフォルトの名無しさん:04/11/20 09:29:06
>>864
( ´・∀・`)へーヘー(´ν_.` )ソウナンダ
866デフォルトの名無しさん:04/11/20 20:44:18
1億 2.25sec
10億 28.609sec

ファイルへの出力方法かえたら半分くらいの時間になった
867デフォルトの名無しさん:04/11/20 21:22:35
大きく変わったね。
868デフォルトの名無しさん:04/11/22 01:40:26
本日は大きな進歩なし 行き詰まりぎみ
気分転換に860のアルゴリズムで作ってみた
結果は1億桁で 5.186sec
現状、エラトステネスより遅いけど、
いいかげんに作ったプログラムなので仕方ない
明日はもうちょっと作りこんでみる
869デフォルトの名無しさん:04/11/22 16:06:07
870デフォルトの名無しさん:04/11/22 16:08:59
>>862
さてはRSALabの因数分解問題を解いて賞金をゲットしようという魂胆だな
871デフォルトの名無しさん:04/11/22 18:00:35
>>870
違うよん
872デフォルトの名無しさん:04/11/23 01:52:37
本日も進歩なし
新しいコードに列挙漏れが発覚
実装ミス
873デフォルトの名無しさん:04/11/24 00:29:35
2,3,5の倍数を除き、1バイトに8個詰めることにより、
30*2^32(1280億)まで拡張可能なコードを書いたが、
1億までのビット計算に4.3s、ファイル出力にさらに7.5s
10億までだと、ビット計算に56.1s、ファイル出力にさらに72.6s
これだと、100億までやると、
メモリ512MB、出力ファイルサイズ5GB、総時間40分くらいかかりそうだ。
874デフォルトの名無しさん:04/11/24 02:10:21
本日も進歩なし
双曲線の漸近線がよく分からん
アルゴリズムの意図しているものが
本当に漸近線なのかもよく分からん

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

一応、僕がエラトステネスやってて思ったことを。
・素数は 6*i+1 6*i+5 にしかないのでそこ以外見ない (>>311)
・なんでか知らんけどx/32という計算のほうがx>>5よりも速い(僕の環境では)
・出力はバイナリ出力でwrite関数とか使うと速い(列挙とはちょっと意味が違うけど)
875デフォルトの名無しさん:04/11/24 07:59:51
874のレベルがとても低いことが分かった。
ようやく言える。日記はチラシの裏にでも書いてろ。
876デフォルトの名無しさん:04/11/24 18:41:00
>>873
ファイル出力遅すぎじゃないか?
877873:04/11/24 19:44:27
for(Loop=0;Loop<Max;Loop++)
{
    if(X[Loop]!=255)
    {
        if((X[Loop]&128)==0)fprintf(fp,"%d\n",30*Loop+7);
        if((X[Loop]&64)==0) fprintf(fp,"%d\n",30*Loop+11);
        if((X[Loop]&32)==0) fprintf(fp,"%d\n",30*Loop+13);
        if((X[Loop]&16)==0) fprintf(fp,"%d\n",30*Loop+17);
        if((X[Loop]&8)==0) fprintf(fp,"%d\n",30*Loop+19);
        if((X[Loop]&4)==0) fprintf(fp,"%d\n",30*Loop+23);
        if((X[Loop]&2)==0) fprintf(fp,"%d\n",30*Loop+29);
        if((X[Loop]&1)==0) fprintf(fp,"%d\n",30*Loop+31);
    }
}
現在のファイル出力部分のコードです。
878デフォルトの名無しさん:04/11/24 23:14:59
そりゃ遅いわ。ビット計算はそれなりなのに勿体無い
879デフォルトの名無しさん:04/11/25 00:27:46
873さんのを取り入れた結果(VCでコンパイル)
1億 1.859sec
10億 23.5sec

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

VCで最適化かけたほうが速いもんだと思ってたんだけど…そういうわけじゃないのね
880デフォルトの名無しさん:04/11/25 00:51:02
速度的にもアルゴリズム的にも見るべきところが無いのだから、
そんな書き込みでスレを荒らさないでくれ。ここは日記帳じゃないんだ。
881マイク ◆yrBrqfF1Ew :04/11/25 05:43:17
日記帳というか便所の落書きじゃなかったか?
882879:04/11/25 07:06:39
でも日記でも落書きでも僕が書いたから
ほかの人もやり始めてくれたんじゃないの?
わかんないけどさ。
ボーっと見てれば
レベルの高い人が見所のあるプログラムを書いてくれるとでも思っているの?
お前ら、すごい人のおこぼれ欲しがってるだけじゃん。
惰性で生きてる人間がモラルなんか持ち出すな。
しょうもない
883デフォルトの名無しさん:04/11/25 08:21:45
>>879
君は最近やり始めて新鮮なのかもしれないが、このスレにとってはなんの価値もない。
本来なら「過去ログ嫁ヴォケ」と一蹴されるはずの内容なんだよ。
荒らし以外のなにものでもないよ。882の書き込みにはある種、感動したけどね。
884デフォルトの名無しさん:04/11/25 09:57:36
・ちまちま書き込まない(ある程度溜めてから一気に書き込む)
・30*Loopは変数で保持
885マイク ◆yrBrqfF1Ew :04/11/25 10:15:21
このスレ自体には何か価値あるか?
886デフォルトの名無しさん:04/11/25 23:57:43
とりあえず名無しで実行時間書くならそのつど、CPU,Memoryは最低限書くべきだと思うのだが…
でないと比較のしようがないと思うのは私だけ?
OS,コンパイラ,コンパイルオプションまで有ればなお良しということで
887デフォルトの名無しさん:04/11/26 21:57:42
>>882-883
このレビューは参考になりましたか?
◎はい ○いいえ
888デフォルトの名無しさん:04/11/26 22:44:40
Pentium4 2.40GHz メモリ256MB VC++ 6.0
1億まで 6.2秒(テキスト形式でファイルに出力)

2と3の倍数を除いてる。6秒切れない…
889デフォルトの名無しさん:04/11/26 23:30:10
わーい、爆速コードの進捗状況と新しいアルゴリズム教えてもらえて嬉しいな
明日もよろしくね
890デフォルトの名無しさん:04/11/26 23:50:36
Pentium4 2.40GHz メモリ512MB VC++6.0
テキストで出力すると1億まで 8.843秒(前のはバイナリで出してた)
あぁ、レベル低いって言われてもしゃあないなぁ…
891デフォルトの名無しさん:04/11/28 14:49:12
890氏のは2、3、5の倍数のみ省いたものなのかな?
892デフォルトの名無しさん:04/11/28 15:46:16
???
893r:04/11/29 23:55:59
エラトステネスの篩。2と3をとばしてある。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1035246186_13/hurui.cpp

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

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

35秒か...
>>890の足下にも及ばんな...
894r:04/11/30 00:00:35
っていうかおまいら、
>>879 一億で1.8秒?!!!!
しかも >>880 速度的に陳腐なの?


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

...λ.......
895r:04/11/30 00:10:20
っていうか、10億なんて

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

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

だれか、
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1035246186_13/hurui.cpp
の、糞な部分を指摘キボン....
896デフォルトの名無しさん:04/11/30 00:50:05
>>895
多分ストリームを使わずprintfにするだけで
かなり縮むと思うぞ。
897r:04/11/30 01:01:11
>>896
それがですな...
std::coutを使用せずに、
カウンタのインクリメントに置き換えてみたんですわ。

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

3倍。
たかだか3倍。
18秒なんて、夢のまた夢
898デフォルトの名無しさん:04/11/30 01:37:21
入出力に時間が掛かっても大した問題じゃないだろうに。
899デフォルトの名無しさん:04/11/30 01:39:49
入出力はスレッドでキュ
900デフォルトの名無しさん:04/11/30 09:23:06
はっきり言うと、相手にするやつが悪い。
901デフォルトの名無しさん:04/11/30 15:16:56
はぁ?
902デフォルトの名無しさん:04/11/30 16:05:21
こんなことになるくらいならさっさと落ちたほうが良かったよ。
903デフォルトの名無しさん:04/11/30 20:51:37
>>895
> inline static prime_t getIndex( prime_t prime ) {
>     return ( ( prime / 6 ) << 1 ) + ( ( prime % 6 ) == 1 );
> }
これが最大のボトルネックだろうなぁ…

> if( i < checkLimit2 && table.check( i += 2 ) ) {
テーブルのサイズを1つ多めに確保しといて、 6i+1 を列挙しなくていい
時はそのビットは立てないようにする。そうすれば i < checkLimit2 はいらない。
904r:04/12/01 02:24:08
>>903
指摘ありがとう。....そうだな。
getIndex()は、確かにボトルネックだな。
探索する空間の広さに比例(いや、n log nか?)して呼び出されるし、
割り算を2回も行っている。

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秒には、全くかなわないけど。
905r:04/12/01 02:33:33
で、いろいろやってみた。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1035246186_14/hurui2.cpp
なんだかすっきりしたが、

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

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

10億で2分半。18秒?ハハッ!
906デフォルトの名無しさん:04/12/01 10:25:32
>>905
コードや環境の違いがあるから一概には言えないかもしれないけど、
check()内で素数を見つけながら出力するより初段ループで篩い分け、
次段のループでテーブル走査の方が早い気がする。
昔書いたコードでは後者の方が早かった(数が大きくなれば逆転するかも)。

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

for(i=1; i<=テーブルのサイズ; i+=3){
  i+i+3とi+i+5をチェック、出力
}
907デフォルトの名無しさん:04/12/02 01:30:44
素数列挙と素数判定はどちらが難しいですか?
908デフォルトの名無しさん:04/12/02 01:50:52
素数を列挙するためには素数かどうか判定しなきゃいけないと思うのは漏れだけですか
909デフォルトの名無しさん:04/12/02 01:56:19
>>908
その必要はない。
ごく簡単なアルゴリズム、例えばエラトステネスのふるい法を考えても、
一つ一つの数が素数かどうか判定していないでしょ。
910デフォルトの名無しさん:04/12/02 02:11:52
そういやそうですな
911デフォルトの名無しさん:04/12/02 12:24:32
Nまでの素数列挙とNの素数判定だったら後者は前者に含まれてる。
Nまでの素数列挙とN^2くらいの大きさの数の素因数分解だと後者の方が簡単だと思う。
少なくとも素数列挙できるレベルのNに関しては。
912r:04/12/04 17:02:57
篩処理と表示を分離したらバナナ問題が発生してしまった。
913デフォルトの名無しさん:04/12/04 20:13:45
読めない
914デフォルトの名無しさん:04/12/04 22:48:40
篩部分を別スレッドにしようとして頓挫
915デフォルトの名無しさん:04/12/06 14:11:24
古い篩
916デフォルトの名無しさん:04/12/07 14:49:23
篩マーケット
917デフォルトの名無しさん:04/12/07 15:19:54
篩発売中
918マイク ◆yrBrqfF1Ew :04/12/07 15:25:33
どのhurui.cppかわからんが23行目でnew[]やったきりdelete[]してないな。
919r:04/12/08 08:41:49
それ俺だ。
しばらく仕事でJavaばっかりだったからうっかりしてたのさ。
その点は修正済み。

これを観てアプリケーション終了時に
deleteすべきかどうかについて興味を持った人は、
よそで議論を。
920r:04/12/18 03:44:13
俺の中で最新の篩。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/33.txt
(ファイルの拡張子がTXTなのは見逃して、UPLOADERの制限なんだ)

% time ./furui3 100000000 > prime_list
9.350u 0.480s 0:10.41 94.4% 0+0k 1+3io 0pf+0w
だいたい1億までの列挙に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
921r:04/12/18 04:40:59
くふう
1. 篩処理と表示処理を分離した
2. いままでは「上限値を超えない」範囲でループを回していたが、
 あらかじめループ回数を計算して、その回数だけ、ループを実行するようにした。
 これによりfor( i = 1; i < [固定値]; i+=[固定値] )という、
 多分一番最適化しやすいループになった。
 (前のは for( i = 5; i < [固定値]; i+=[可変値]) )
 ほんとに最適化しやすいのかどうかは知らない。
3. 2により、「整数」の世界と「6n+1/6n+5」の世界の間の
 数値の変換が減った。
4. 表示にprintfを使わないようにして、
 文字列表示用のクラスを導入した。1億までで、4秒くらい稼いだ
5. 今までは、素数を見つけたあと、その素数の倍数にmarkする処理の
 ための増分値の基底として「見つけた素数の6倍」の値を使っていたが、
 これを「見つけた素数の4倍」と「見つけた素数の2倍」の両値の
 排他的論理和を使う事にした。
 これで探索可能範囲が61ビットから62ビットまで増えた
6. 素数そのものを示すためのprime_tと、配列の添字の為の
 index_tを明確に分離した。
 
922r:04/12/18 04:51:35
で、改善したいポイントが一つ。

えっと、整数をを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マクロを、呼ばなくていいようにしたい。
923r:04/12/18 05:09:26
どうすればPRIME_TO_INDEXマクロを呼ばなくていいようになるかと言うと、
p(n,b)の値の5倍、7倍、11倍、13倍、17倍、19倍...の値を
簡単に見つける方法があればいい。

今はどうしているかと言うと
1. p(n,b)で表現された整数値(Iとする)を得る。
2. Iの4倍値 inc4とIの2倍値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の、2個めの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 );
}
924デフォルトの名無しさん:04/12/18 08:29:06
過去ログ読まないの?
読んだ上で低レベルな話してるの?
発言するより、過去ログ読んだり人のコード見たりしたほうがいいよ。
925デフォルトの名無しさん:04/12/18 10:14:46
正直ループ内で割り算を使う理由がわからない。2と3の倍数を除く基本アルゴリズムはこうでしょ。
6n-1のn=1でふるう。
(6n-1)(6n+1)=6(6n^2)-1
(6n-1)(6n-1)=6(6n^2-2n)+1
よって、6n-1側は、6個目から5個おきにふるう。
6n+1側は、4個目から、5個おきにふるう。
6n+1のn=1でふるう。
(6n+1)(6n+5)=6(6n^2+6n+1)-1
(6n+1)(6n+1)=6(6n^2+2n)+1
よって、6n-1側は、13個目から7個おきにふるう。
6n+1側は、8個目から、7個おきにふるう。
n=2では、
6n-1側を、6*2^2=24個目から11個おきにふるう。
6n+1側は、6*2^2-2*2=20個目から、11個おきにふるう。
6n-1側を、6*2^2+6*2+1==37個目から13個おきにふるう。
6n+1側は、6*2^2+2*2=28個目から、13個おきにふるう。

これより速いやつあるぅ。
926デフォルトの名無しさん:04/12/18 11:21:29
printf("2, 3, 5, 7, ..................., ->∞\n");
927デフォルトの名無しさん:04/12/18 11:48:22
メモリが有限なので実行できません。
928r:04/12/23 13:14:47
>>924
見たけど、よくわかんねーんだよ

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

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

そしたら >>925 のあげてるのと同じになった。
俺、理解していないのに。なんか不思議。
929r:04/12/23 13:20:52
で、これがそれ。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/40.txt

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

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

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

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

% 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
931デフォルトの名無しさん:04/12/25 13:40:46
正直もういいから
な!930
932r:04/12/25 14:18:35
>>931
ここは広告の裏だ。

な?わかるか?
933デフォルトの名無しさん:04/12/25 14:32:17
まだまだ改良の余地あり。

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

# OperaとかUDとか起動しまくり状態。
934デフォルトの名無しさん:04/12/25 15:31:06
このスレってネタがネタだけにリアル中高生が多い予感。
935デフォルトの名無しさん:04/12/26 00:02:00
>>932
>>930で9秒切れるんなら>>929でも切れるんじゃないか?
936デフォルトの名無しさん:04/12/26 00:17:30
go( )の中の i のループも工夫できそうだね
937デフォルトの名無しさん:04/12/27 01:52:11
#include <stdio.h>
#include <stdlib.h>

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

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

int TestBits(unsigned char *tbl,unsigned int bit)
{ return tbl[bit>>3] & (1 << (bit &7));
}
void SetBit(unsigned char *tbl,unsigned int bit)
{ tbl[bit>>3] |= (1 << (bit &7));
}
938デフォルトの名無しさん:04/12/27 01:53:40
unsigned char * PrintPrime( unsigned int nn )
{
const n = nn - (nn % 6 == 0 || nn % 6 == 5 ? (nn + 1) % 6 : nn % 6 - 1);
const MAX3=(n+2)/3;
unsigned char * tbl = malloc(MAX3);
unsigned int m=1,n1,n2, x;
 memset(tbl,0,MAX3);

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

 return tbl;
}
939デフォルトの名無しさん:04/12/27 01:55:45
int main(int argc, char *argv[]){
  if(argc != 2) return 1;
  PrintPrime(atoi(argv[1]));
  return 0;
}

428を改造したコードだよ。君のと比べてみ。
君みたいな厨が現われないように859を書いたんだよ。
今となってはこのスレ、落とすのも埋めるのも変わらないかもね。
940939:04/12/27 02:51:51
あ、桁溢れ忘れてた。
whileの条件の中は m < sqrt(MAX3/3) で、抜けたあとに
 for(; m < MAX3; m++)
   if(!TestBits(tbl, m))
     PutsInt(m);
て感じで。
mallocの中はMAX3/7くらいで。
941デフォルトの名無しさん:04/12/27 18:18:28
>>875
>>880
>>883
>>92
>>931
同一人物かどうか知らないが、お前(ら)が一番邪魔。
942デフォルトの名無しさん:04/12/27 18:19:04
>>92 --> >>924
943939:04/12/27 19:27:43
教えてくれ、悪意のないバカが日記を書き始めたらどうしたらいい。
君は頭なでなでして飴玉あげたいのかい? 俺にそんな母性本能はないよ。
そうなんないように早めに「最低428」ってハードルを作っといたんだよ。
そしたら平気でそのハードルくぐってきやがった(笑い)。
まあ、こういうのも含めて2ちゃんねるなわけだが。
もういいよ、止めないから埋めてくれ。
944デフォルトの名無しさん:04/12/27 20:40:10
悔しい。>>939に500ミリ秒負けてしまった。
945r:04/12/27 22:58:18
>>943
悪意の無い馬鹿が日記を書き始めたらどうしたらいいって?
放置すりゃいいんじゃね?

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

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

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

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

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

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

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

まあ、俺は939のコードに1億までの列挙で1200msecほど負けたので
もそっと精進しますが。
946デフォルトの名無しさん:04/12/27 23:17:51
>>943
考え方はいろいろあるだろうけど、
やる気のある人間がやる気のない人間のスペースを奪うというのは
2ch的というより一般的な現象だね
君が向上しようとしていないから、どうすればいいかも分からないんだろうし、
泣いて哀れみ誘うしか止める手段がないんだろうね
947デフォルトの名無しさん:04/12/27 23:59:11
1億1.8秒のコードはどうも怪しい気がするんですが俺だけですか。
948デフォルトの名無しさん:04/12/28 00:11:06
>>947
単なるマシンパワーなんじゃないの?
949デフォルトの名無しさん:04/12/28 01:52:03
unsigned char * PrintPrime( unsigned int nn ){
const n = nn - (nn % 6 == 0 || nn % 6 == 5 ? (nn + 1) % 6 : nn % 6 - 1);
const MAX3=n/3; unsigned char * tbl = malloc(MAX3/8); unsigned int m=1,n1,n2, x;
memset(tbl,0,MAX3/8);
while (m <= sqrt(MAX3/3)){
if(!TestBits(tbl, m) ){
x = m*(3*m+4)+1;
n2 = 6*m+4; n1 = 2*m+1;
PutsInt(3*m+2);
while( x<MAX3){SetBit(tbl, x); if(x+n1>=MAX3) break; SetBit(tbl, x+n1); x += n2;}
} m++;
if(!TestBits(tbl, m) ){
x = m*(3*m+2);
n2 = 6*m+2; n1 = 4*m+1;
PutsInt(3*m+1);
while( x<MAX3){SetBit(tbl,x); if(x+n1>=MAX3) break; SetBit(tbl,x+n1);x+=n2;}
} m++;
}
for(; m < MAX3; ){
if(!TestBits(tbl, m)){
PutsInt(3*m+2);
}m++;
if(m >= MAX3) break;
if(!TestBits(tbl, m)){
PutsInt(3*m+1);
}m++;
}
return tbl;
}
950デフォルトの名無しさん:04/12/28 02:03:02
939はいろいろ間違ってたので上は修正版。
改行減らすために見にくくなってしまった。
>>946
過去のコードを読まないなんてすごいやる気だね。
俺やる気ないからそこまで適当に発言できないわ。
そんな漏れのコードはこれ
http://primes.dnip.net/primes.tar.gz
>>859 にある5番目のテクニックを使うともっと早く
なるんだけど、あんまり綺麗じゃないから実装前のやつ。

しつこく保守してるヤシがいるなあと思ってたのに...
951デフォルトの名無しさん:04/12/28 07:29:40
なんもやらなかった人間にくらべりゃどんなやつだってやる気あるだろ。
「〜と思ってました」
「自分が望んだのはこんなんじゃありません」
「私は暗にこういうことを伝えたかったんです」
「好きにすればいいです」
なんもせずにそういう言葉を平気で吐ける人間と
実際にがんばる人間だったらがんばる人間を応援したくなるよ。
952デフォルトの名無しさん:04/12/28 08:10:06
無駄ながんばりなんだよな・・・

風邪引いて仕事してて
「あー私風邪でも仕事がんばってるなー」
なんて寝言ほざいてる馬鹿と一緒じゃん
迷惑なんだよ
と何度いいそうになったことか
自分中心で考えてて
周りのことを考えることができないんだろうなと思った。
953デフォルトの名無しさん:04/12/28 11:19:04
>>952
風邪で仕事来ないでください。伝染ります。
954r:04/12/28 13:49:14
で、>>949 のコードを見てみたんだが、
「見つけた素数の倍数を、マークする(ふるう?)処理」って言うのは
√maxまででいいんだな。
そりゃそうか、
素数pをみつけたとき、pより小さい素数の倍数って言うのはすべてマークしてある。
つまり「pとp小さい素数の積」ってのはすべてマークしてある。
ってことはpの自乗よりも大きい数だけ、マークすればいい。
ってことは√maxよりも大きい素数を見つけた時は、
マークすべき数が無い、ってことか。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/47.txt

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

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) にあるだろう。
これが漏れの中で飲み込めたら、実装しようと思う。

955デフォルトの名無しさん:04/12/28 13:55:10
なにも調べないで他人のスペースを奪うやつが「やる気ある人」、「がんばる人間」。
煮詰まって発言が少なくなったやつは「やる気ない人」、「なんもやらなかった人間」。
やる気ないスレにやる気ある人が書き込んでんだから足引っぱるんじゃねえ。

過去ログ読めないやつのための859だった訳だがそういう問題じゃなかったと。
956r:04/12/28 16:48:52
さて、>>950のコードでも読もうか...

漏れの環境で
% time ./primes -p 100000000 > prime_list
9824 + 65536 = 75360
3.840u 0.630s 0:04.81 92.9% 0+0k 0+1io 0pf+0w
1億まで4.8秒?...漏れが学ぶべきポイントは多そうだ
957r:05/01/16 18:14:30
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/77.txt

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

% time ./furui11 1000000000 > prime_list11_2
60.270u 5.740s 1:08.57 96.2% 0+0k 0+49io 0pf+0w
958デフォルトの名無しさん:05/01/18 19:17:04
planet risk見たいと思ったが。
radeon9000proで見れんかった。
グラボはみんな何で見てる?
demo起動->ゲフォ必要->電源落としてカード取り替え&ドライバ再インスコ->( ゚Д゚)ウマー
このくらいの気合があれば良いんだろうけど・・・・
959デフォルトの名無しさん:05/01/19 09:04:29
グラフィックカードに素数列挙させるの?だったら凄そう。
960デフォルトの名無しさん:05/01/28 08:56:09
SSE使えないかな
961デフォルトの名無しさん:05/01/30 18:02:35
awe
962r:05/02/05 10:57:22
少しコードを削ってみた。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/183.cpp

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

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

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

2、3の倍数だけを抜いた方が、2、3、5を抜いた篩よりもコードが単純になる分最適化が効きやすかったりして有利かとも思ったが、
やはり859にあるように2,3,5を抜いた方が探索空間が小さい分だけ有利なんかなあ。
コードの単純さだと、950のは相当単純な反復に落としてあるし。
963デフォルトの名無しさん:05/03/02 18:14:54
保守野鉄郎
964デフォルトの名無しさん:2005/03/22(火) 19:27:31
CPU換装したら、ここで試せや↓
http://www5e.biglobe.ne.jp/~liquor/prime/
965デフォルトの名無しさん:2005/03/28(月) 22:23:35
これ、動かないよ?アクセスバイオレーションとか
966デフォルトの名無しさん:2005/03/28(月) 23:02:22
primeベンチか、VC++6で作られてるから、
古すぎて動かないやつもいるのかもね
作者が古いのか、OSが新しすぎるのかw
967デフォルトの名無しさん:皇紀2665/04/01(金) 08:36:10
MAC用もキボン
968デフォルトの名無しさん:2005/05/09(月) 09:15:30
新たな参戦を求む
969デフォルトの名無しさん:2005/05/09(月) 20:52:19
さいしょから2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97の倍数を抜いちゃったら?
970デフォルトの名無しさん:2005/05/13(金) 20:17:49
>>969
やってみれ
971デフォルトの名無しさん:2005/05/29(日) 15:20:17
                    , -=- -─‐-、
                   _ ´-─ ¬く  ̄  ̄ミ- 、
                ,,,,/    _==-ミァ-─‐-、 \''''''''''''ー--、,,,,,_
            _,,,,-''"/  , ‐''"         \ \、_,,,ー''ゞ" `ゞ、
            -' "  /  /     /   |      \ ヽ     /"`
       _,,-''''''"""''''' / /  /   / /    ||  |  i  ヽ i    /
       ´"''、.    i /  / /  / / /    ||  ||  |│ |ノス  /
          '、   |//  / /___, -一ァ|  /! |ト、|│ | | く」/
            '、  |,-‐¬  ---┘'7 |!  ハ! |,、-┼十|!/\/\
          , -‐ ''"  し' '´_ /,ィ二l |ト、/!ヽト、\_ヽ!|!l\:..  /
       ,r/      __   ,イ|リ ヾハ! ヽ!  ,ィ⌒ヾミリノ/:::... \
      / ||ヽ  -'     / ̄ )` __      |ヒノ:} '` ,;\/\/
    ,r '   ヾ、  ,-、____ , イ ̄,r==-      ==-'  レ' /|  |
  / ヽ    `ーソ  ' | |ト、,ヘ ′""          "" / / || |
. /    \_  /  | ハ ヽ`゙'ヘ       ' '     / / | |  |       1000GET
           /   / / |  ヽ 川\      0     //! |  | |  |
        /    / / 八  \川| |`ト- .. __ , イ‐ァヘ |  | ||  |!
      /    / / /  \  \ 「`ー- 、    /  .〉  ト、|  ヽ、
     ,イ    /-─=¬ニヘ、_  \   厂\ 厂ヽ /!|   | `ー=ヘ
 -‐  ̄ /─ '  ̄     ├- ヽ\  \ノ\ \ 人 ハ!ヽ ||  |-┤ ヽ
      /          /!‐-- | |\   ト、_`ヽ oヽ  ト、!  ||  |‐┤- ヽ
  // 〉      __ /  ├‐-  ||  | 川-‐  | |  厂7! ハ!  ├:┤  ̄ヽ
  / / ー ─    ̄       ├‐- リ  || ハ!ヘ   | |  ト┤|/′ ヾ,┤   ゙i_
  ‐ '              〉‐-    | / /\ .|o | /ヽ/(′    ∨     \
972デフォルトの名無しさん:2005/05/29(日) 17:24:58
2,3だと6のうち2つ
2.3.5だと30のうち8つ
2,3,5,7だと210のうち48
973デフォルトの名無しさん:2005/05/29(日) 23:33:09
ΠpのうちのΠp-1
974デフォルトの名無しさん:2005/07/08(金) 22:17:42
974get
975デフォルトの名無しさん:2005/07/09(土) 09:03:08
2種類の分銅A,Bを使って、じゃがいも1gの物を量るために
成分A,Bを求める、またその正当性も求めるというアルゴリズムは
どのようにかけばいいのでしょうか?
知ってる方いましたらどうかおしえてください。
976デフォルトの名無しさん:2005/07/09(土) 13:32:00
>>975 マルチ士ね
977デフォルトの名無しさん:2005/07/09(土) 16:52:50
>>976
知らないならほっといてください。
知ってる方いましたら
どうかおしえてください。
978デフォルトの名無しさん:2005/07/09(土) 18:18:23
拡張ユークリッドの互除法
979デフォルトの名無しさん:2005/07/09(土) 23:51:05
拡張ユークリッドの互除法
は最大公約数を求めるものですよね?
それをどういうふうにつかえばよろしいのでしょうか?

980デフォルトの名無しさん:2005/07/09(土) 23:59:03
自分勝手なやつだな。
ほっといたら迷惑なんだよ、お前は。
ここにいちゃいけない人間なんだってことを理解しろ。
981デフォルトの名無しさん:2005/07/10(日) 01:23:14
>>980それは君
いくつものスレに迷惑文ばっか載せて
他人迷惑をかけている。

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

オメ
982デフォルトの名無しさん:2005/07/10(日) 03:32:38
テラキモス
983 :2005/07/10(日) 14:59:50
984デフォルトの名無しさん:2005/07/10(日) 15:51:40
>>934
むしろ神父さん。
985デフォルトの名無しさん:2005/07/11(月) 02:01:03
>>982
あ〜
怖くなったのか。
986デフォルトの名無しさん:2005/07/11(月) 02:14:24
カコイイ!トオモテルノカナジブンデワ
987デフォルトの名無しさん
>>986あなたは利用規約に反しています。
再三の忠告にも関わらず
迷惑行為をしていますので
利用規約違反者として
あなたの通信記録より身元を判明させて頂き、
警察等に連絡させていただきます。