5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :1:02/04/13 09:24
メモリとかも考慮に入れた超高速なアルゴリズムを真剣に考えるスレ

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

2 :デフォルトの名無しさん:02/04/13 09:26
宿題?いや、卒業研究と言ったところか?

3 :デフォルトの名無しさん:02/04/13 09:30
>>1
挙げるべきかじゃねーよ
スレ立てるなら参考ページからソフト、
関連技術などのリンクそろえておけ

4 :デフォルトの名無しさん:02/04/13 09:36
暗号ソフトをつくるんじゃないのか?それを元に


5 :デフォルトの名無しさん:02/04/13 09:41
>>1
既存スレ
   最速の素数判定アルゴリズム  
http://pc.2ch.net/test/read.cgi/tech/993457354/

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

6 :1:02/04/13 09:45
>>2
どっちでもないです。

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

素数算出系ソフト
http://www.lycos.co.jp/cgi-bin/pursuit?query=%91f%90%94&cat=jpdownload&maxhits=17&qs=gt|rate,gt|nflg

7 :1:02/04/13 09:47
>>5
判定と列挙は微妙に違います。向こうで書くと微妙にスレ違いになりそうだったので。

8 :デフォルトの名無しさん:02/04/13 09:52
>>7 まあいいけど、 あっちのスレも半分以上は列挙の話題だよ

9 :デフォルトの名無しさん:02/04/13 10:03
>>6
そこのリンク、ものすごく低レベルなんだが、
もしかして10桁とか20桁とかそういうものすごい低レベルな話?

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

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

10 :1:02/04/13 10:10
>>9
そのとおりです。凄く低レベルです。
数百万桁クラスの素数を列挙する方法があるんですか?

11 :デフォルトの名無しさん:02/04/13 10:14
>>10
作ったこともない奴が作った奴を批判する資格はない。

12 :デフォルトの名無しさん:02/04/13 10:17
>>10 そんなもんがあったら驚天動地

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

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

14 :デフォルトの名無しさん:02/04/13 10:33
そこらへんは フルイの使い方だけの問題だからなあ

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

15 :デフォルトの名無しさん:02/04/13 10:35
>>12
64bit限界はエラトステネスのふるいを使った場合

16 :1:02/04/13 10:40
>>14
100桁の素数辞書のサイズが莫迦にならないと思うんですが…

17 :デフォルトの名無しさん:02/04/13 11:00
>>16 だから 指定した100桁程度の素数から  28bit程度のフルイビットマップで表現すればいいでしょ?

18 :デフォルトの名無しさん:02/04/13 11:03
>>15 他には巧い方法は無いと思うけど? 何かある?

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

19 :デフォルトの名無しさん:02/04/13 11:06
テーブル引き

20 :デフォルトの名無しさん:02/04/13 11:29
32Bitの最大の素数って何?1個か2個素数がほしい。

21 :デフォルトの名無しさん:02/04/13 11:35
2^32 - 5


22 :デフォルトの名無しさん:02/04/13 11:36
もう1個欲しいなら 2^31 -1 も素数だから


23 :デフォルトの名無しさん:02/04/13 14:21
じゃ課題を
n0 := 170141183460469231731687303715884105727

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


24 :デフォルトの名無しさん:02/04/13 19:51
あれ? もう1はヘタったの?

2^127-1 = 170141183460469231731687303715884105727


25 :デフォルトの名無しさん:02/04/15 11:48
>>24 1ではないが 計算が終りません・・・(涙

26 :デフォルトの名無しさん:02/04/18 20:12
>>1-all
てめえらここにソース出してみろ

27 :デフォルトの名無しさん:02/04/18 20:14
CUBEって映画思い出した

28 :デフォルトの名無しさん:02/04/18 21:00
>>26
オマエモナーって言ってほしい?

29 :デフォルトの名無しさん:02/04/19 08:46
age

30 :デフォルトの名無しさん:02/04/19 20:17
数値じゃなくて速さを極めるのでもいいの?

31 :デフォルトの名無しさん:02/04/19 21:19
>>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/

ここはちょっと違うよー

36 :デフォルトの名無しさん:02/04/20 16:24
平凡な素数判定って奇数をふるいにかけて残ったやつ、でよい?
プログラムの練習で書くような場合。

37 :デフォルトの名無しさん:02/04/20 17:29
>>36
いいんじゃない? てか俺それ以外に思いつかない。

38 :デフォルトの名無しさん:02/04/20 18:10
列挙のばあい、倍数に非素数のマークつけるのはダメなの?

39 :デフォルトの名無しさん:02/04/20 18:23
>>38
もちっと詳しく説明きぼんぬ。

40 :デフォルトの名無しさん:02/04/20 22:11
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るぞ

42 :デフォルトの名無しさん:02/04/20 22:52
>>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
あげ

46 :デフォルトの名無しさん:02/04/21 12:22
ttp://www.prime.net/prime.html
に63bit以下の素数全部載ってるよ

47 :デフォルトの名無しさん:02/04/21 12:23
ページが見つかりません
検索中のページは、削除された、名前が変更された、または現在利用できない可能性があります。


48 :デフォルトの名無しさん:02/04/21 13:49
 

49 :デフォルトの名無しさん:02/04/22 02:45
age

50 :デフォルトの名無しさん:02/04/22 17:50
>>48
つまんね

51 :クレジャパン:02/04/22 18:18
素数てなんですか?>>1



52 :ヽ(´ー`)ノ:02/04/22 18:20
プログラム言うより数学だろ

53 :デフォルトの名無しさん:02/04/22 19:31
>>51
荒らしは氏ね

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

54 :デフォルトの名無しさん:02/04/22 21:29
>>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){
で判定するから速さはあんまり変わらない気がする。

57 :デフォルトの名無しさん:02/04/22 21:51
>>40 フルイを作る時は テーブルの√最大値の迄で作れる

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

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


58 :デフォルトの名無しさん:02/04/22 21:51
>>57
あっそうか!
自分が前に作ったのは小さい素数から順にファイルに保存してくやつだったから。。。
エラトステネス使ってたら意味ないか。。。


59 :58:02/04/22 21:54
>>56です

60 :デフォルトの名無しさん:02/04/22 21:54
>>58 その
   最速の素数判定アルゴリズム  
http://pc.2ch.net/test/read.cgi/tech/993457354/

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

61 :デフォルトの名無しさん:02/04/22 22:06
>>57
C初心者なのでソースが読めません…

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

63 :デフォルトの名無しさん:02/04/22 22:20
こっちはもうちょいレベル低く行きましょう(^^;
実は>>40書いたの俺なんです…

64 :デフォルトの名無しさん:02/04/22 22:23
>>62
除く処理がちと面倒…かな?

65 :デフォルトの名無しさん:02/04/22 22:36
質問!
6の倍数に1足したら素数確定ですか?

66 :デフォルトの名無しさん:02/04/22 22:46
>>65
25=6*4+1

67 :デフォルトの名無しさん:02/04/30 13:45
あげ

68 :デフォルトの名無しさん:02/05/22 01:02
この手があったか!?
ttp://f1.aaacafe.ne.jp/~pointc/log59.html

セコイのでsage

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

70 :デフォルトの名無しさん:02/05/23 02:26
Haskellだと

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

だな。

71 :デフォルトの名無しさん:02/05/23 02:27
>>68
「なんでもあり」なのに is_prime 使ってるのはなんでだろう?

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

でよくね?


72 :デフォルトの名無しさん:02/05/23 12:22
実行ファイルのサイズがすごそう
小さい数字まで求めたいとき、プログラムのロード時間の方が大きくなって…

73 :Delフサギコ ◆zE1iiRdQ :02/05/23 13:08
        ∫        _____________
   ∧,,∧ ∬       /フォルダわけて分割したテキストファイルを
   ミ,,゚Д゚ノ,っ━~  <  読み込んだ方がいいよ。
_と~,,,  ~,,,ノ_. ∀  \_________
    .ミ,,,/~),  .| ┷┳━
 ̄ ̄ ̄ .し'J ̄ ̄|... ┃  どこまでか知らんが
 ̄ ̄ ̄ ̄ ̄ ̄ ̄   .┻  素数列を32bitIntegerMaxまで持ったら256MBとか512MB
               程度のメモリが必要だったんじゃなかったかな。

74 :デフォルトの名無しさん:02/05/23 14:48
>73
ということは、100Mオーバーのアプリになるのか イヤン

75 :デフォルトの名無しさん:02/05/23 16:32
>>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

78 :デフォルトの名無しさん:02/05/24 00:31
>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
忘れてた。

84 :デフォルトの名無しさん:02/05/24 09:14
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 を追加。

87 :デフォルトの名無しさん:02/05/24 21:10
>>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
興味あります。教えてください。

91 :デフォルトの名無しさん:02/05/25 05:41
>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
レヴェル高いなー

94 :デフォルトの名無しさん:02/05/25 21:31
>>93
や、実はその分野を勉強した人にとっては初歩の初歩なんよ。
専門分野が違う人に「おれって頭良いでしょ」とかますハッタリとしては
効果的なんだけどさ。

95 :デフォルトの名無しさん:02/05/25 21:34
初等代数学の本に載っているから教養レベルだったかな
数学科だけかもしれないけど

96 :デフォルトの名無しさん:02/05/26 13:10
>>94-95
そうなのか…ちょいと鬱だ
漏れはエラトステネスを2飛ばしでやるのが精一杯だYO...

97 :デフォルトの名無しさん:02/06/01 22:20
保守

98 :デフォルトの名無しさん:02/06/11 21:43
ageてみたり

99 :Lisp 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
速さはいかほどでしょう?

101 :Lisp 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変数の多項式で、整数の値を入れた時、値が正になる限り素数
だったような...
全部求められなくとも、巨大な素数をいち早く見つける方法としては
有効かも.

105 :デフォルトの名無しさん:02/06/13 04:37
>>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/

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

109 :デフォルトの名無しさん:02/07/22 05:05
保守

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の配列の練習問題との違いは、素数であることが確定したら
すぐ出力されること。

112 :デフォルトの名無しさん:02/07/29 20:58
>>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 です。

115 :デフォルトの名無しさん:02/07/30 05:18
ttp://f1.aaacafe.ne.jp/~zxrg/software/psrch.html
ここ参考になるかな?

116 :デフォルトの名無しさん:02/08/01 17:13
このソースの鑑定求む
http://www.kurims.kyoto-u.ac.jp/~ooura/pc_bench/prime.c


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のコードが理解できない…

120 :デフォルトの名無しさん:02/08/08 21:09
保守

121 :デフォルトの名無しさん:02/08/10 00:38
age

122 :多項式時間:02/08/10 11:24
 

123 :デフォルトの名無しさん:02/08/10 20:39
もはや多項式時間なので、ハードウェアの進歩を待つのが吉というデフレスパイラル

124 :デフォルトの名無しさん:02/08/13 03:36
>>117
sqrt()や乗算を使いたくなかったのだろう。
ビットを多用しているのはメモリ節約の為(1/32か)。
普通にエラトステネスの篩を使った場合と比べて速くなるかは微妙だな。

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

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

126 :デフォルトの名無しさん:02/08/14 02:25
2と3の倍数を飛ばすエラトステネスは結構速くなるね。

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

127 :デフォルトの名無しさん:02/08/14 05:31
インドアルゴリズムを改良すれば論文にできるね。

128 : ◆.RANK1Kg :02/08/14 16:22
ひぇっ、指名されたw

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

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

129 : ◆.RANK1Kg :02/08/14 16:29
素数判定に使われるアルゴリズム(確率的でも決定的でもいいですが)って、
素数表を必要としないのが特徴ですが、
素数列挙の場合は自然数Nが素数か調べるときにN未満までの素数表が使えます。

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

130 :デフォルトの名無しさん:02/08/14 16:31
>>126
URL見るだけでエラトステネスだってわかるけど

131 : ◆.RANK1Kg :02/08/14 16:36
>>130
1度作ってみると分かりますよ。
素数表を保持する性質上、メモリの無駄を抑えるところで差がつくんです。

132 :デフォルトの名無しさん:02/08/14 17:00
>>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;
}

133 :デフォルトの名無しさん:02/08/14 17:02
あ、一箇所インデント狂った

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
素数生成多項式ならずううーーーーと前からあったよ。

136 :デフォルトの名無しさん:02/08/15 09:26
>>135 それが何か関係あるの?

137 :デフォルトの名無しさん:02/08/16 14:16
#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より頭いい。

138 :デフォルトの名無しさん:02/08/18 19:42
>>134>>137も、>>68で概出なのよ



139 :デフォルトの名無しさん:02/08/24 19:10
http://pc3.2ch.net/test/read.cgi/tech/983191866/910-911
でも外出

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
M.E@9.DUZ=!-`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
ぐぐれば終わりだろが。
http://gt.sakura.ne.jp/~nyagy/integer/sosuu_seisei.html

145 :デフォルトの名無しさん:02/08/25 00:32
>>144
ワロタ。

146 :デフォルトの名無しさん:02/08/25 09:58

やったぜ、素数見つけた

147 :デフォルトの名無しさん:02/08/28 23:35
素数10000個列挙に20秒、
60000個列挙に12分。
これってどう?全然戦えてない?

148 :デフォルトの名無しさん:02/08/29 02:20
>>147 dame
Vectorあたりで何個か落としてみろ

149 :デフォルトの名無しさん:02/08/29 02:22
>>147
10000個目、60000個目の素数が何だか知らんが
1000000までの素数を列挙する(ちなみに素数の数は78498個)のに
400MHzのCPUで0.75秒。

150 :デフォルトの名無しさん:02/08/29 02:23
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に移植してみたのれす。。
# でも・・・・・遅いっすね★

156 :デフォルトの名無しさん:02/08/30 00:55
>>◆DhJkQxJw
俺はRubyのコトはよく分からんのだが過去レスに色々ソースがあるから
見てみ(大概Cだけど)。

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

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

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

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

158 :デフォルトの名無しさん:02/08/30 14:44
>>157
しばらくすると消えるから必要なレスをコピペして。
http://pc3.2ch.net/test/read.cgi/pc3tr/1030500162/


159 :デフォルトの名無しさん:02/08/30 15:40
正直、どこをどう読めば活躍してるのか分からない。
頑張って勉強していたスレ、というなら認めるが。
活躍というなら、>>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よりは早いのれす。
求めた素数をすべて配列に保持するアルゴリズムを
実装すると、かえって速度が落ちるようなのれす。
うひひ。

162 :デフォルトの名無しさん:02/08/30 22:56
>>160
無駄レスするな。暗躍の意味をわかっているのか小一時間。

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

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

164 :デフォルトの名無しさん:02/08/30 23:06
こんな奴が俺より年上なのか、情けない。

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

165 : ◆DhJkQxJw :02/08/30 23:08
>>164
うひひ★どうせ漏れはドキュソれすよ★
ドキュソはドキュソらしくしてるのが
一番なのれすよ★
ハァァ・・・

166 :デフォルトの名無しさん:02/08/30 23:19
>>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

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

168 :デフォルトの名無しさん:02/08/30 23:39
>>167 試合放棄?
そうか、ここまでよく頑張ったな。いいよ。

169 : ◆DhJkQxJw :02/08/30 23:41
・゚・(ノД`)・゚・ウワーン
いぢめっこがいるよ〜★

                 ┌─┐
                 |も.|
                 |う |
                 │来│
                 │ね│
                 │え .|
                 │よ .|
      バカ    ゴルァ  │ !!.│
                 └─┤    プンプン
    ヽ(`Д´)ノ ヽ(`Д´)ノ  (`Д´)ノ    ( `Д)
    | ̄ ̄ ̄|─| ̄ ̄ ̄|─| ̄ ̄ ̄|─□( ヽ┐U
〜 〜  ̄◎ ̄  . ̄◎ ̄   ̄◎ ̄   ◎−>┘◎

170 : ◆MAKNgZ1Q :02/08/30 23:53
はじめまして〜☆
こんばんわ〜☆

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

171 :デフォルトの名無しさん:02/08/31 00:00
面白くない。

172 :デフォルトの名無しさん:02/09/03 15:08
保守

173 :デフォルトの名無しさん:02/09/03 18:00
>>172
ていうか、sageてない?

174 :デフォルトの名無しさん:02/09/03 18:18
>>173
sageのまま保守することがいけないことか?

175 :デフォルトの名無しさん:02/09/03 22:01
>>174
禿同!!

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

176 :デフォルトの名無しさん:02/09/03 22:09
>>175
そういいながらageて書く君が好きだ

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

177 :デフォルトの名無しさん:02/09/03 22:50
>>176
やってみれば。
小手先の技でも塵も積もれば山となる…かも

178 :デフォルトの名無しさん:02/09/05 21:16
そうだな

179 :DQN.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は素数じゃねぇよ

182 :デフォルトの名無しさん:02/09/06 02:16
>>181
馬鹿はあんただよ…

183 :デフォルトの名無しさん:02/09/06 02:18
おばかさん1は素数じゃねぇよ

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

184 :デフォルトの名無しさん:02/09/06 02:37
8 * 9=31
は  く さい
白菜

185 :デフォルトの名無しさん:02/09/07 11:07
めっちゃ素直にふるいを実装。
% 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」がバイナリ。
最初の引数が、ふるいの大きさ。
次の引数で、いくつめの素数を表示するかを指定( チェック用 )

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

186 :デフォルトの名無しさん:02/09/07 12:04
>>185 頑張ってくれ。俺はこれといった面白いアイデアが無い。

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

187 :DQN.cc:02/09/07 14:36
>>185
改造したらソースきぼ〜ん☆

188 :デフォルトの名無しさん:02/09/11 22:22
ソースがいっぱい

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

189 :デフォルトの名無しさん:02/09/11 22:28
>>188
数はあるけど…

190 :188:02/09/11 22:33
まぁ、プログラミングの練習の段階ですから

191 :185: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行にもなっちゃった。

192 :デフォルトの名無しさん:02/09/13 03:24
あぷろだにうp!

193 :デフォルトの名無しさん:02/09/13 03:41
数が大きくなればなるほど素数の出現頻度は低くなるの?

194 :デフォルトの名無しさん:02/09/13 04:43
>>191
凄く厨な事聞いてるみたいで恥ずかしいのだが、
>1.940u 0.400s 0:02.55 91.7% 0+0k 0+0io 0pf+0w ( G4 450MHz )
これの読み方がわからぬ(;´Д`)
何が何を表してるのか教えてくだされ。。

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

196 :デフォルトの名無しさん:02/09/13 09:55
>>193
π(x)〜x/log(x)なんだそうな。
だからちょっとずつ頻度は低くなる。

197 :デフォルトの名無しさん:02/09/13 15:47
>>195
ファイルが見つかりません…

198 :デフォルトの名無しさん:02/09/13 15:51
http://tool-ya.ddo.jp/2ch/trash-box/file/20020913081215032.gz
これはどなた?

199 :185: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 :デフォルトの名無しさん:02/09/14 01:34
200 get!っと

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

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

201 :185:02/09/14 23:03
>>200
っていうか、漏れアフォなので、
一個のメソッドが30行くらいを越えると、
全然理解できなくなっちゃうのです。


202 :デフォルトの名無しさん:02/09/15 00:14
誰かmainにまとめたバージョンうpきぼんぬ

203 :デフォルトの名無しさん:02/09/15 00:34
age

204 :デフォルトの名無しさん:02/09/15 01:31
>>202
七行スレに依頼しる!

205 :デフォルトの名無しさん:02/09/15 01:36
>>204
見づらさが500%増加の見込み

206 :ソースを読まずにカキコ:02/09/15 02:26
出入りの激しいループの奥深くの関数以外は速度面から見てもベタ書き不要。
コンパイラによってはinline指定子もあるし。

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

207 :デフォルトの名無しさん:02/09/15 02:42
>>206 正論だな


208 :デフォルトの名無しさん:02/09/17 00:56
素数なんて列挙してどうするの?

209 :デフォルトの名無しさん:02/09/17 01:02
>>201
30行?カスだな。

210 :デフォルトの名無しさん:02/09/17 01:54
>>208 より速く、より高く、より遠くへ。男のロマソだ。

211 :デフォルトの名無しさん:02/09/17 02:28
>>210 同意
シンプルな問題ではあるが、奥が深い
素数自体がおもしろい数だし

212 :デフォルトの名無しさん:02/09/17 21:52
>>208
賞金もらえるぞ

213 :デフォルトの名無しさん:02/09/17 22:42
そこに素数が(可算個)あるからだ。

214 :デフォルトの名無しさん:02/09/20 21:05
hoshu

215 :デフォルトの名無しさん:02/09/24 18:35
限界目指してます

216 :デフォルトの名無しさん:02/09/28 03:01
ほっしゅ

217 :デフォルトの名無しさん:02/09/30 12:57
列挙ってことは、配列かなんかに
素数を全部入れなきゃ駄目?

218 :デフォルトの名無しさん:02/09/30 14:19
>>217 標準出力とかに順番にヌケも間違いも無く出せればそれでいいと思うよ。

219 :デフォルトの名無しさん:02/09/30 15:18
>>217
速さを目指すなら、バイナリでファイルに出力することを推奨

220 :デフォルトの名無しさん:02/09/30 21:15
最後は可読な状態で出力がいいな。
バイナリだと何でもありになりそうだから…

221 :デフォルトの名無しさん:02/09/30 21:20
>>220
出力0.0001秒、表示200時間とか?

222 :デフォルトの名無しさん:02/09/30 21:28
んなのがあるかい

223 :デフォルトの名無しさん:02/09/30 22:00
>>220
そうだな。
じゃあテキストで、tab 又は 改行で区切るってことで。

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

224 :デフォルトの名無しさん:02/10/01 01:20
素数なんか列挙して何になるの?

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

225 :デフォルトの名無しさん:02/10/01 01:33
>>224
禿しく慨出。

226 :デフォルトの名無しさん:02/10/01 01:37
>>224
数学は列挙したりなどしない。定義さえすれば、そこにあるものだから。
そして利用する場合には、プログラム的なアクセスが必要になる。

227 :デフォルトの名無しさん:02/10/01 01:40
板違い。

228 :デフォルトの名無しさん:02/10/01 02:51
数学とプログラム、特にアルゴリズムは深い関係があるのを知らないのかい

229 :デフォルトの名無しさん:02/10/01 07:08
素数列挙列挙ではあんまり数学的なテクニックが使えないからねえ。

230 :デフォルトの名無しさん:02/10/03 22:45
素数列挙って言うと、
1:エラトステネスの篩
2:順番に素数判定
の二つしか知らないのだけど、もっと素敵な列挙法ってないでしょうか?


231 :デフォルトの名無しさん:02/10/04 22:31
>>230
素数データベースから読み出して表示
(列挙は列挙でしょ♪)

232 :デフォルトの名無しさん:02/10/05 00:50
enumerate of prime numbers.

233 :デフォルトの名無しさん:02/10/05 01:36
適当な奇数を表示して問いかける。

234 :デフォルトの名無しさん:02/10/07 23:32
>>233
意味が良くわかんないんだけど。
説明していただけるかしら?

235 :名無しさん ◆jZGaCDQNcc :02/10/07 23:44
>>234

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

236 :デフォルトの名無しさん:02/10/08 01:50
それは、>>230の2に該当ということでいいのか

237 :デフォルトの名無しさん:02/10/08 21:22
結局エラトステネスが一番素敵だと思う。
プラス2の倍数を飛ばしてみたり。

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

238 :名無しさん ◆jZGaCDQNcc :02/10/08 22:32
>>237
「2の倍数」って・・・。


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

239 :デフォルトの名無しさん:02/10/08 22:51
>>237 胴衣

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

240 :デフォルトの名無しさん:02/10/08 23:46
あと如何にメモリの使用量を抑えるかですな

241 :デフォルトの名無しさん:02/10/10 01:10
数学板より
http://science.2ch.net/test/read.cgi/math/1033486518/
http://science.2ch.net/test/read.cgi/math/1030077269/


242 :デフォルトの名無しさん:02/10/10 06:26
>>237
無限に存在する素数を相手にする時に限界があるよね。
2の倍数、3の倍数の枝刈りのようなもの。

243 :デフォルトの名無しさん:02/10/11 01:39
>>242
俺たちにゃ有限の時間しか残されていないのだから、有限でいいのさ

244 :デフォルトの名無しさん:02/10/12 07:14
ピタゴラス数を列挙(・∀・)シヨーヨ
a²+b²=c²な数を!

245 :デフォルトの名無しさん:02/10/12 08:36
[{3,4},{5}]

246 :デフォルトの名無しさん:02/10/12 10:50
bracket brace three comma four brace comma brace five brace bracket

247 :デフォルトの名無しさん:02/10/12 19:02
>>244
それセンター試験でやった。懐かすぃ

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


249 :名無しさん ◆jZGaCDQNcc :02/10/13 10:03
>>248
どのコードよ?

250 :248:02/10/13 10:05
書き込もうと思ったが、長過ぎたようだった。

251 :248: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 という名前で。

252 :248: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 。


253 :248: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 という名前で。


254 :248: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 オプションをつけて、コンパイルした。


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

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


256 :名無しさん ◆jZGaCDQNcc :02/10/13 11:19
>>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になると数十秒待っても終わらなかった。

どっちばれ。

257 :名無しさん ◆jZGaCDQNcc :02/10/13 11:22
全部を一ファイルにまとめている。

#!/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


258 :名無しさん ◆jZGaCDQNcc :02/10/13 11:23
>>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


259 :名無しさん ◆jZGaCDQNcc :02/10/13 11:24
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


260 :名無しさん ◆jZGaCDQNcc :02/10/13 11:24
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

261 :名無しさん ◆jZGaCDQNcc :02/10/13 11:24
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

262 :248:02/10/13 11:41
>>256
実行環境を教えて下さいませ。

263 :名無しさん ◆jZGaCDQNcc :02/10/13 11:57
>>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
結局エラトステネスしかないってわけか。

265 :名無しさん ◆jZGaCDQNcc :02/10/13 12:02
ただし、同じ環境でも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

266 :デフォルトの名無しさん:02/10/18 01:54
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;
}


269 :デフォルトの名無しさん:02/10/19 15:53
何がじゃ

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

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

期待していますよ。

271 :名無しさん ◆jZGaCDQNcc :02/10/20 13:30
ところで、数学のこと全然知らないDQNなんだけどさぁ、

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

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

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

272 :デフォルトの名無しさん:02/10/20 13:43
>>267
引用してよぅ。すごい興味あります...

273 :デフォルトの名無しさん:02/10/20 14:34
>>271
関数の形で素数を表現するだけでしたら、
集合 {y | gcd(1,y)=1, y!=1} に順序を与えればよいってことで。

274 :デフォルトの名無しさん:02/10/20 14:53
{y|IsPrime(y)=true}

275 :名無しさん ◆jZGaCDQNcc :02/10/20 15:01
>>273
うーみゅ。数学に詳しくないからあれなんだけど、
ある程度の数まで有効な素数ジェネレータがないか
ってことなのれす。。。

276 :デフォルトの名無しさん:02/10/20 15:50
昔どっかの掲示板で、
「任意の有限の数列を表現する 一般的な方法」
をみた気がする。


277 :デフォルトの名無しさん:02/10/20 17:20
ハァハァ・・・うーみゅ・・・(;´Д`)
ハァハァ・・・エトラステネス!(・∀・)

278 :エトラストテトラストステネス:02/10/20 17:27
>>277


279 :デフォルトの名無しさん:02/10/20 17:32
>277
不安になってググッちまったよ。
残念ながら、エトラステネスでは一件もヒットしなかった。

280 :デフォルトの名無しさん:02/10/20 17:33
>>275

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

281 :もまずにパピコ:02/10/20 17:39
>>279
エストラテネスなら2件ヒットしたぞ。

282 :デフォルトの名無しさん:02/10/20 17:52
>>280
>>275が欲しがっているのはシーケンシャルな計算なしで、
一発で( O(1)で )素数を求めるための式でしょ。


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

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

284 :名無しさん ◆jZGaCDQNcc :02/10/20 18:22
>>282
たとえば
 (A) n + 1
ならnが1から2までなら成り立つっしょ?

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

285 :デフォルトの名無しさん:02/10/20 19:49
メルセンヌ何とかやらとか…
確かものすごい次数の式になった気が。

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


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

286 :名無しさん ◆jZGaCDQNcc :02/10/20 19:58
>>285
いや、だから100までとか1000までとかの間に
限って成り立つ式なら簡単な数式でも
ありそうなものだと思ったわけでつ。。。

287 :デフォルトの名無しさん:02/10/21 13:49
自分で作れば?
100までの素数を解にもつ多項式なら作れるじゃん。
たとえば10までだったら
(x-2)(x-3)(x-5)(x-7)=0
これが>>286がほしい方程式じゃん。

288 :デフォルトの名無しさん:02/10/21 13:51
ごめん、関数と方程式間違えた。。。

289 :287: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だろうがいけると思う。
素数がわかってなきゃ解けないから意味ないけど。

290 :287:02/10/21 14:27
っていうかラグランジュ補間とかニュートン補間でいけるか。
何度も書き込みすまそ。

291 :268: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;
}

292 :デフォルトの名無しさん:02/10/21 20:23
成長があまり見られん

293 :デフォルトの名無しさん:02/10/22 03:00
while(0){
fprintf(stdout,"計算中です!!(止めないで)");
fprintf(stderr,"(次の素数をお願いします…(こそーり))");
scanf(&x);
fprintf("あ?次の素数?%dに決まってんだろボケ",x);
}

294 :Delフサギコ ◆A6VzDeLphI :02/10/22 09:32
素数列挙してよし。
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1035246186
            _____________
   ∧,,∧    /
   ミ,,゚Д゚彡 <  書いてみたです。
   ,;゙   ミ     \ 
 @ミ,,,UUミ       ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
       エストラの2の倍数/3の倍数を使ってみますた。
       そんなに高速化できませぬですた。

295 :エトラストテトラストステネス:02/10/23 02:25
>>294
だから、エストラとかかかないでよ!
どれが正解だか解んなくなるしさ!

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

296 :Delフサギコ ◆A6VzDeLphI :02/10/23 13:07
 ミ,,゚Д゚ミつ...反応が、、、、ニャイ、、、、だれかコードのあれとか、、、
                     コメントないの?

297 :デフォルトの名無しさん:02/10/23 13:14
>>296
1億 or 10億 or 2^31 or 2^32 以下の素数を求めるのにかかかる時間と実行環境オセーテ


298 :エトラストテトラストステネス:02/10/23 22:56
>>296
すまん。つーか、コード長過ぎて、見る気がせん。
のんきな人だったら、週末まで待ってくれ。

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


299 :Delフサギコ ◆A6VzDeLphI :02/10/23 23:50
            _____________
   ∧,,∧    /
   ミ,,゚Д゚彡 <  すごく遅いはずよ。
   ,;゙   ミ     \ 
 @ミ,,,UUミ       ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
ビットごとで素数か否かを判断して
2の倍数と3の倍数を削除してるだけだから。
ドノーマルのフルイです
メモリ使用量は少ないので.
容量が必要でオチるのはないと思うですが

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

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

300 :Delフサギコ ◆A6VzDeLphI :02/10/24 00:51
 ∫,,,,,,,,,∧,,∧   300ゲト
⊂,,,,,,,,,つ,,゚Д゚ミつ
        このスレ、、住人少ないの?

301 :デフォルトの名無しさん:02/10/24 02:01
6ヶ月でレスが300というのは、少ない方だろう

302 :Delフサギコ ◆A6VzDeLphI :02/10/24 15:34
 ∫,,,,,,,,,∧,,∧   3日経っても
⊂,,,,,,,,,つ,,゚Д゚ミつ Int32.Maxまでの素数は
           求まっていなかった,,,もしかしたら300日くらいかかる?

303 :デフォルトの名無しさん:02/10/24 19:30
>>302 ガンガレ

304 :デフォルトの名無しさん:02/10/25 07:37
こっちに書きます。
>どうせなら 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を足すようにすると、
 コードは増えますが、その実行サイクルはメモリアクセスに完全に隠れてしまいます



305 :デフォルトの名無しさん:02/10/25 08:03
チラっと見たけど 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;

306 :デフォルトの名無しさん:02/10/25 08:06
なお、TestIsPrimeの中で偶数ならfalseを返していますが
速度を考えるならホントはループ中に入れない方がいいです。
偶数でも値が2の時はTrueを返すとかの処理も

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

307 :Delフサギコ ◆A6VzDeLphI :02/10/25 11:12
             ___________
    ∧,,∧     /
   ミ,,゚Д゚彡 <  さんくすこですー
   ミ つ日   \___________
 .@ミ,,,,,, ,,ミ
>それをMove関数を使ってコピーし、
理論は理解しました。
でも。その初期化処理を具体的に
どう実装するのかがわからんですの。

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

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

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

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

詳しい説明ありがd

308 :デフォルトの名無しさん:02/10/25 12:10
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

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


310 :デフォルトの名無しさん:02/10/25 13:06
と色々書いたけど、実際にはこういう事をやっても1分でも計算時間を短くするのは難しいです。

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

311 :デフォルトの名無しさん:02/10/25 16:32
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とループします


312 :デフォルトの名無しさん:02/10/25 16:36
忘れていました。
 2,3の倍数を表から除いた場合、
セットすべきビット位置は x div 3 で 求まります。

313 :デフォルトの名無しさん:02/10/25 18:16
コードとしてはこんな感じです。 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にしておいた方がいいです

314 :Delフサギコ ◆A6VzDeLphI :02/10/25 18:25
>>312
function TPrimeListTBitsTripleOverCompress.AccessInsideIndex(
 OutSideIndex: Integer): Integer;
begin
 Result := ((OutSideIndex div 6)*2)
      +
      ((OutSideIndex mod 6) div 5);
end;
こんな感じだと思ってたのですが、
これって、x div 3 なのでしょうか?

|,,∧  ・ ・ ・ ・ 
|Д゚彡
| U
| ミ    
| U

315 :デフォルトの名無しさん:02/10/25 18:31
>>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になりますね?

316 :Delフサギコ ◆A6VzDeLphI :02/10/25 18:57

|,,∧  アラヤダ すごいわぁ
|Д゚彡
| U
| ミ   

317 :デフォルトの名無しさん:02/10/25 19:05
>>314
除算は整数でも浮動小数点ユニットが使われたりで、並列演算が出来ないから
そういうふうに連続して使わない方がいいよ。 合計3つも連続して使うとストールする。

318 :Delフサギコ ◆A6VzDeLphI :02/10/25 20:09
|,,∧   素数列を文字列でスペース区切りしたらMaxInt32で
|Д゚彡 ファイルにして、1ギガになちゃう勢いなんですが
|⊂ミ  …
| ミ    Webにウプする場所がない…
|''U そもそも、俺の56K回線では…

319 :デフォルトの名無しさん:02/10/25 20:59
誰かCに翻訳してくれ…意味がわからん。・゚・(ノД`)・゚・。

320 :デフォルトの名無しさん:02/10/25 21:18
>>318 そんなもの計算させる前に見積もりさせないとさあ

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

321 :デフォルトの名無しさん:02/10/25 21:24
とだけ書くと、単なる煽りなので
0〜N を10進で改行付で列挙する場合のおよその必要バイト数
 
N*(log10(N)+2)/loge(N)
l

322 :デフォルトの名無しさん:02/10/25 21:41
>>319
どのコードを?

323 :デフォルトの名無しさん:02/10/25 21:50
>>322
>>305,308,313
つまり全部…

324 :デフォルトの名無しさん:02/10/25 22:32
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;
}

325 :デフォルトの名無しさん:02/10/25 22:34
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);
 }
}

326 :デフォルトの名無しさん:02/10/25 22:37
ありゃ こうか
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

328 :デフォルトの名無しさん:02/10/25 22:59
>>304
どこから来たの?どのような概念?

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

ゴメン、詳細キボン

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

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

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

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


330 :328: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)です。

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

332 :デフォルトの名無しさん:02/10/26 21:52
更に混乱した

333 :デフォルトの名無しさん:02/10/26 22:02
確かに>>.324は速いね。 最速かな?

334 :デフォルトの名無しさん:02/10/26 22:12
>>333
そんなに速いの? バイナリupキボン

335 :デフォルトの名無しさん:02/10/26 22:20
>>334
GCCでもBCCでもコンパイル出来るだろ

336 :デフォルトの名無しさん:02/10/26 23:15
>>334
フサギコのコードより倍のサイズを列挙してるのに、3桁以上速い

337 :デフォルトの名無しさん:02/10/26 23:45
具体的にどのくらい早いの?

338 :デフォルトの名無しさん:02/10/27 00:09
たぶん2千倍くらいじゃない? 想像だけど


339 :デフォルトの名無しさん:02/10/27 00:36
エラトステネス 対 除算なら千倍ちかく差がでるのは分かってたけど
エラトステネス同士でも実装次第で千倍くらい変わるんだ へぇ

340 :Delフサギコ ◆A6VzDeLphI :02/10/27 00:37
 ミ,,゚Д゚彡 
私も自分のコードを1000倍くらい高速化したですよ。

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

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

341 :デフォルトの名無しさん:02/10/27 01:52
>>340
まずInt32MaxIntって書くより 2^31-1 って書いてくれた方が判り易いよ

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

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

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


342 :Delフサギコ ◆A6VzDeLphI :02/10/27 03:04
            _____________
   ∧,,∧    /
   ミ,,゚Д゚彡 <  さらさらっとそういう計算できるのって
   ,;゙   ミ     \ なかなか頭の切れがよいですね。
 @ミ,,,UUミ       ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
2^31-1 = 2147483647
2^63-1 = 9223372036854775807

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

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

343 :デフォルトの名無しさん:02/10/27 09:18
>>342
例の定理が正しいとすれば
50年先ですから、生きてる間に見える可能性は高いかな・・・いや、CPU速度が追いつくのはさらに倍か

344 :デフォルトの名無しさん:02/10/27 10:54
6ヶ月でレスが300というのは、少ない方だろう

345 :デフォルトの名無しさん:02/10/28 00:46
だーかーらー。
http://pc3.2ch.net/test/read.cgi/tech/983191866/910-911
が最速なんだってば。

346 :デフォルトの名無しさん:02/10/28 01:13
>>345
とりあえず10億まで計算させてみろ! 話はそれからだ

347 :デフォルトの名無しさん:02/10/28 13:22
>>345
(0〜2^31) という条件だと、難しいんでは?

348 :デフォルトの名無しさん:02/10/28 16:26
132番目の素数はもう出たの?

349 :デフォルトの名無しさん:02/10/28 16:35
>>348

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


350 :デフォルトの名無しさん:02/10/28 16:47
std::pow(2, 743)-1

4.62686e+223

(・∀・)?

351 :デフォルトの名無しさん:02/10/28 16:50
46268644699475435470014199270680622913148582491776246164412857235254375716637876222457838321585848270371190628323884999935972095850551557285913445801770125007762163162852820919462003875720454598226040577701224945512200798207

352 :デフォルトの名無しさん:02/10/28 17:41
なんで224桁もあやふやにならずに書けんだよ!
と問いたい。おっぱいを突付きながら問い詰めたい。

353 :デフォルトの名無しさん:02/10/28 17:43
UBASICを使えば簡単

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

354 :デフォルトの名無しさん:02/10/28 21:00
>>352
俺にも突っつかせろ

355 :デフォルトの名無しさん:02/10/29 01:11
>>353
「132番目の素数さん」は数学板のデフォルトの名無しさん。
132番目の素数が743(名無しさん)であることから。

356 :デフォルトの名無しさん:02/11/05 02:08
浮上

357 :Delフサギコ ◆A6VzDeLphI :02/11/07 12:54
                _____
      ∧,,∧___   /
    /ミ゚Д゚,,ミ/\<  とりあえずupッときまつた
  /| ̄∪∪ ̄|\/ \_____
    |____|/

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

358 :デフォルトの名無しさん:02/11/07 18:37
ところで、Vectorにあるような素数列挙ソフトと比べるとどう?
素数xpとか。

359 :デフォルトの名無しさん:02/11/07 20:36
そりゃ全然かなわないよ。
1兆も計算出来るという事は 37bitの計算が出来るわけだし。

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

360 :デフォルトの名無しさん:02/11/07 22:37
>>359
>>113が近い?

361 :デフォルトの名無しさん:02/11/07 23:37
OO さいこー!!

362 :Delフサギコ ◆A6VzDeLphI :02/11/08 10:14
            _____________
   ∧,,∧    /
  _ ミ,,゚Д゚彡 _< unsinedint最大まで求めるってのは
.=| |=U===U=| |= \いいかもしんない
 | | .ミ   ミ | |     ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 | |ノ∪''∪. | | しかし…もう篩いの容量が
         劇的には減らないですねー

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


363 :デフォルトの名無しさん:02/11/08 10:33
2^34 = 171 7986 9184

171億 7986万 では?


364 :Delフサギコ ◆A6VzDeLphI :02/11/08 11:13
            _____________
    ∧,,∧    /
  _ ミ,,  彡_<  ゲーム脳で頭が腐ったみたいです。
.=| |=ミ   ミ=| |= \
 | | ミ@ ミ | |     ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 | | ∪''∪ | | 鬱だ。
 | |      | |
          

365 :デフォルトの名無しさん:02/11/08 11:23
2^32 -1 迄のは >>324で出るようだが?

366 :デフォルトの名無しさん:02/11/08 11:53
篩の結果を 算術圧縮したらどうなるんだろ?
圧縮する時の係数を n bit目を 1/log(n) としたら、ほぼ完全な乱数になるのだろうか?

367 :デフォルトの名無しさん:02/11/08 20:05
おいデルフサー
てめーああん?


カワイイじゃねえか、乳揉むぞコルァ

368 :デフォルトの名無しさん:02/11/08 22:22
>>362
一気に計算する必要はないんよ。
過去ログにそういうアルゴリズムがあった。

369 :デフォルトの名無しさん:02/11/09 01:15
>>362
Del使ってないからわからんのだがunsinedintってなに?
unsignedintの親戚かなにかか?

370 :名無しさん ◆jZGaCDQNcc :02/11/09 01:18
>>369
もう★ そんな野暮なこと聞くなんて
おちゃめさんなんだからぁ♪

371 :Delフサギコ ◆A6VzDeLphI :02/11/09 02:13
            ∫    _________
   ∧,,∧     ∬   /
   ミ,,゜Д゜彡っ━~  < 安心Edintを知りませんか?
_と~,,  ~,,,ノ_.  ∀   \ 
    ミ,,,,/~), │ ┷┳━   ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ .じ'J ̄ ̄| ┃
 ̄ ̄ ̄ ̄ ̄ ̄ ̄  ┻

       ∫         _____________
   ∧,,∧ ∬       /
   ミ,,-Д-ノ,っ━~  < ・・・ 俺も知らない・・・
_と~,,,  ~,,,ノ_. ∀   \
    .ミ,,,/~),  .| ┷┳━   ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 ̄ ̄ ̄ .し'J ̄ ̄|... ┃
 ̄ ̄ ̄ ̄ ̄ ̄ ̄   .┻
>>368
使わない所の古いはHDに退避させとくのですか?
速度とかの辛味で難しそうですね。

372 :デフォルトの名無しさん:02/11/09 14:39
>>126 のソースコードの作者だけど、Delフサギコ さんのソース良さげな感じ。
そのうちアイディア取り入れさせて貰います。

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

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

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

ただし、

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

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

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

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


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

373 :デフォルトの名無しさん:02/11/09 17:27
>>372
あのリンク貼った者です。まさか降臨なされるとは。

374 :Delフサギコ ◆A6VzDeLphI :02/11/09 17:55
   すごいっす。
     .Λ,,Λ.  ___  
    ミ;゚Д゚ミ .||::::::::||
    ミ   つ___||_____|| 
   | ̄ ̄|__ミ―――――
   `ー┬‐''
     ┴
>エラトステネスの篩いにおいて、ある数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が素数って判定した後は
それをどこかメモリに貯めておかなければならないのかな???
いや、、求めた瞬間にファイル出力したらいいのか...

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

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

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

376 :Delフサギコ ◆A6VzDeLphI :02/11/09 18:02
いや、そうじゃなかったですか。

> 逆に言えば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も抜きたいけど,,,
いったい、どうやるんだろかしら、、、、まだまだ奥深いです。

377 :デフォルトの名無しさん:02/11/09 18:14
落ち着け。

378 :372 ◆2ZUH6PwhYk :02/11/09 20:47
どうも言葉が足りなかったようで、分かりにくくてすみません。
>>376で仰ってる通りの感じです。

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

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

379 :Delフサギコ ◆A6VzDeLphI :02/11/10 12:42
            _____________
   ∧,,∧    / 試行錯誤したり
   ミ,,゚Д゚彡 <  実装したりして、いろいろ
   ,;゙   ミ     \ わかってくるものっすね。
 @ミ,,,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以外の素数のある個所を除いたテーブルを用意して
それを篩のビットを消す時に使うようにする。


381 :Delフサ: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


382 :デフォルトの名無しさん:02/11/13 23:06
あってるみたいだね。おめでとう。
しかし30時間もかかるもんなのか…

383 :デフォルトの名無しさん:02/11/18 20:03
保守っとく

384 :Delフサギコ ◆A6VzDeLphI :02/11/19 12:59
  ,,,,,,,,,,,,,∧,,∧   /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


386 :デフォルトの名無しさん:02/11/20 01:57
素数の2乗を6で割った余りは必ず1である

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

387 :誰か:02/11/20 13:39
50000までの素数を求めるプログラムをCで組んでくれませんか? おながいします

388 :デフォルトの名無しさん:02/11/20 13:46
ごめん、日本語の読めない厨房をここへ誘導してしまいました
回線切って、首釣ってきます...

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
ありがとぅございました

391 :Warez:02/11/20 15:57
セミコロン1つくらい省略しておけばよかったのに・・.

392 :誰か:02/11/20 16:01
厨は逝けや

393 :デフォルトの名無しさん:02/11/20 21:47
>>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)

395 :デフォルトの名無しさん:02/11/21 21:16
高速化&圧縮
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)

396 :デフォルトの名無しさん:02/11/22 16:56
2^32-1までの素数をファイルに出力するのに、
AthlonXP 1800 メモリ 512MB で 2分50秒くらい
Pentium2 400MHz メモリ 128MB で 14分くらい
ってどうですか?

397 :デフォルトの名無しさん:02/11/22 21:42
>>396
健闘してるんじゃない? >>150といい勝負かも

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

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

399 :デフォルトの名無しさん:02/11/23 02:12
>>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
天進法かよ!

403 :デフォルトの名無しさん:02/11/23 17:41
>>400
それは知っているよ。

404 :403:02/11/23 17:46
小さい方からの素数の最少公倍数ごとに区切っていくものでしょ。

405 :403訂正:02/11/23 17:52
少=>小
なんでこんなバ化なんだ家の辞書(バ化だって・・・TOT)

406 :403:02/11/23 17:55
>>400を使った場合、
この前発表された公式と、どう比べたら良いのか、詳細希望。

407 :デフォルトの名無しさん:02/11/24 01:34
>>406
「この前発表された公式」と言うのはインド人が見つけたアルゴリズムのこと?

408 :デフォルトの名無しさん:02/11/24 16:03
>>407
そうかもしれない。あっちは素数一つを求める事が出来るとかか?


409 :408:02/11/24 16:05
[列挙]が付いているからな、
このスレタイには

410 :デフォルトの名無しさん:02/11/24 17:19
判定のほうは随分前にdat落ちしたからね

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

412 :デフォルトの名無しさん:02/11/25 21:21
>>411
ファイル出力ありの記録希望

413 :396ではないが:02/11/25 22:06
ファイルシステムが違うので、比較不能と思われ

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


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

416 :デフォルトの名無しさん:02/11/26 00:00
ソースきぼん

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

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

私もソースきぼん。

418 : ◆2ZUH6PwhYk :02/11/26 02:14
× ご丁寧に除算してくれてたけど。
○ ご丁寧に二回除算してくれてたけど。

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

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

421 :デフォルトの名無しさん:02/11/26 22:49
VCだとコンパイルできないのね

422 :デフォルトの名無しさん:02/11/27 00:16
1億まで(ファイル出力あり)
>>324 52秒
>>419 50秒
K6-2 400MHz

423 :396: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 でいいのかな?
余裕を取っただけでは?


425 :396: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;
}

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

427 :デフォルトの名無しさん:02/11/27 15:28
>>425は毎回 n1,n2類の計算をしてるけど>>324は素数の時だけしてるからでは?

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

428 :396: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;
}

429 :396:02/11/27 18:13
>>427
確かにそうですね。でも428でも遅いんですけど、なんか間違ってるかなあ。


430 :デフォルトの名無しさん:02/11/27 20:39
単純に、アライメントが変わったからじゃないの?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

432 :デフォルトの名無しさん:02/11/30 17:49
アスロン1700+で1億まで求めたら24分かかった・・・
( ゚д゚)ポカーン

433 :432:02/11/30 19:32
改良しても7分半かかった・・・
( ゚д゚)ポカカーン


434 :デフォルトの名無しさん:02/11/30 21:57
ただいま作成中・・・。

435 :431:02/12/01 00:25
>>432
main()の
for ( n = 1 ; n < 65536 ; n += 1 ) {}
nの値を1億に変えてませんか?
分かり辛いですが、このままで 2^32-1 までを求めてます

436 :431:02/12/01 00:35
>>432
直接1億にしたら、もっと時間が掛かりそうですね…
取りあえず、各値を変えないで、実行してみてください

437 :432: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秒切れるというのはマジすか???

439 :デフォルトの名無しさん:02/12/01 14:41
>>438
最適化のオプションをいじくるとか

440 :123:02/12/01 15:20
VB最強ってことか・・。

441 :デフォルトの名無しさん:02/12/01 15:47
>>438
ここVB製。
http://f1.aaacafe.ne.jp/~zxrg/

442 :デフォルトの名無しさん:02/12/01 16:55
419から5の倍数も除いたもので、
AthlonXP 1800 で 20秒
Pentium2 400MHz で 2分11秒
ぐらいでした。

443 :他スレの297:02/12/01 17:07
改良して10万なら2秒。100万までなら43秒・・・(VBで)。
>>441のものには全然敵わない・・・くそ!!!

444 :432:02/12/01 17:19
>>443
もしかして除算型のアルゴリズム使ってない?
エラテネシのほうが早いよ。

445 :他スレの297:02/12/01 17:33
エラテネシって何すか?
検索したけれども・・・ない。

446 :デフォルトの名無しさん:02/12/01 17:37
>>445
エラトステネス

447 :デフォルトの名無しさん:02/12/01 17:57
  ( ・∀・)   | | ガッ
 と    )    | |
   Y /ノ    人
    / )    <  >__Λ∩
  _/し' //. V`Д´)/ ←>>444
 (_フ彡        /

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

449 :デフォルトの名無しさん:02/12/09 21:29
保守

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;
}
}
}
//続く

451 :450: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;
}


452 :450: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;
}


453 :デフォルトの名無しさん:02/12/11 22:20
これは遅いですか?

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

454 :デフォルトの名無しさん:02/12/11 23:20
>>453
除算型の中でも遅い方だと思う。

455 :デフォルトの名無しさん:02/12/12 04:38
>>453
Cのコンパイラ持っていないので分かりません。
どれぐらい時間かかった?

456 :デフォルトの名無しさん:02/12/12 09:35
2、3日かかりそうで怖いな

457 :デフォルトの名無しさん:02/12/12 22:25
知ってたらすまそ〜ん。
今日会社で仕事中に思いついたいい方法を書くよ〜ヒントだけど。
(ちなみにオイラはこの方法でしこたま短縮した)

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

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


458 :デフォルトの名無しさん:02/12/12 22:31
>>457
しこたま速くなるんじゃなくてしこたま遅かったんだろ。お前のが。

459 :デフォルトの名無しさん:02/12/12 22:31
全然進歩しないね
これが2chの限界

460 :457:02/12/12 22:32
>>458
そうだよ。
>>459
お前に言われたくない。

461 :デフォルトの名無しさん:02/12/12 22:35
エラトステネス以上のアルゴリズム、誰か知らない?

462 :デフォルトの名無しさん:02/12/12 22:45
>>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 :デフォルトの名無しさん:02/12/13 05:00
素数って上限の有無はまだ確定してないですよね?

466 :デフォルトの名無しさん:02/12/13 05:04
>>465 無限にあることが証明されている。

467 :デフォルトの名無しさん:02/12/13 05:33
なるほど。
つーことはリストに照らし合わせる必要がある限り、
無限のメモリが必要か。

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

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


468 :デフォルトの名無しさん:02/12/13 05:38
そんなこと考えるよりさ
漏れたちでエラトステネスより
オーダの小さいのアルゴリズムを
考え出せばいいのさ

469 :464:02/12/13 05:43
>>467
勉強の為に作っただけなので、とりあえず1万桁でいいです。


470 :デフォルトの名無しさん:02/12/13 05:44
そいやどこかに、今のスパコンでどのくらいかかるか出ていたっけ。
ってことは、おおよそ見当はついているのか。

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


471 :デフォルトの名無しさん:02/12/13 05:49
素数の判定に他の素数との割り算を必要としないアルゴリズム?

472 :457:02/12/13 18:26
>>471
だから、割り算をすると遅くなるんだよ。
発想の転換をしようや。

473 :デフォルトの名無しさん:02/12/13 18:31
エラトステネスのどこに割り算を使うんだ?

474 :デフォルトの名無しさん:02/12/13 19:51
>>472
このスレ全部読めよ

475 :デフォルトの名無しさん:02/12/14 05:09
>>473
任意のn〜mまでの素数を列挙する時じゃねえか?

476 :デフォルトの名無しさん:02/12/14 15:39
>>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 (デカイのでナローバンドな人は注意!!)


479 :デフォルトの名無しさん:02/12/14 15:55
おそらく↑の平方根までの素数は出尽くしてるかと。

480 :俺(数学者崩れ):02/12/14 16:17
>>477
ミスった。VBでファイル出力しないと0.66秒台
ま、大した事無いが・・・。

481 :デフォルトの名無しさん:02/12/14 16:26
>>477
VBはちゃんと最適化してるか?

482 :俺(数学者崩れ):02/12/14 16:41
>>481
幾ら探してみても俺のVB6.0には最適化オプションが無い。
参ったね♪

483 :デフォルトの名無しさん:02/12/14 16:50
アカデミック版とか?

484 :デフォルトの名無しさん:02/12/14 23:09
>>476
2^32 〜 2^32 + 2^31 のように大きな数を列挙する場合は
除算を使った方が良いだろ

485 :デフォルトの名無しさん:02/12/14 23:25
あぁ、確かに2、3回除算使ってるな>範囲列挙

486 :デフォルトの名無しさん:02/12/15 04:00
>>457も分かってないが>>485も何処で必要になるか分かってないだろ

487 :デフォルトの名無しさん:02/12/15 04:40
>>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;
}
}




489 :488: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;
}
//かなり速いと思うが、どうよ?

490 :デフォルトの名無しさん:02/12/15 15:41
つーか過去ログ読んでないやつ多すぎ。
324(関数部分は428でも可)ぐらい、短いんだからすぐ読めるだろう。

491 :デフォルトの名無しさん:02/12/15 15:49
>>490
お前は何も解っていないんだな???
2と3の倍数を最初から除いておいて何の意味があるんだ???
だったら5も7も、11も最初から除いておけよ。
アルゴリズム、って意味を知ってるか???お馬鹿ちゃん。

492 :デフォルトの名無しさん:02/12/15 15:58
>>491
どのコードのどの「アルゴリズム」が324より優れているのか説明キボン

493 :デフォルトの名無しさん:02/12/15 15:58
>>490
同意。
>>491
何で必死なの?

494 :デフォルトの名無しさん:02/12/15 18:36
>>491
アルゴリズムをそっくりそのまま使う人ですか?

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

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


496 :デフォルトの名無しさん:02/12/15 19:16
>>495
勘違いですね

497 :デフォルトの名無しさん:02/12/15 19:16
>>495
意味不明

498 :デフォルトの名無しさん:02/12/15 19:18
ここですか。
「アルゴリズム」の意味を理解していないデジドカの集うスレは。

499 :デフォルトの名無しさん:02/12/15 19:19
>>496 >>497
馬鹿二人(藁

500 :デフォルトの名無しさん:02/12/15 19:31
>>495
もう少し分かりやすく説明してもらえると・・・

501 :デフォルトの名無しさん:02/12/15 19:31
>>495
たしかに2や3が最初から素数かどうかなんてコンピュータはわからないわけだから
アルゴリズムとしてはおかしい
けど実践的なのは事実

502 :デフォルトの名無しさん:02/12/15 19:33
>>501
それをアルゴリズムの間違いとするのは、おかしいだろ?
「アルゴリズムのクラス(or プロパティ)として、ユニバーサル性を欠く」
ということなら、わからないでもないが。

503 :501:02/12/15 19:34
× それをアルゴリズムの間違いとするのは、おかしいだろ?
○ それをアルゴリズムがおかしいとするのは、間違いだろ?

504 :502:02/12/15 19:34
たびたびすまん。503は502である。

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

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

507 :デフォルトの名無しさん:02/12/15 19:42
>>505
意味不明な言葉で誤魔化さないようにしましょう。

508 :デフォルトの名無しさん:02/12/15 19:42
>>505
速い方が必ずしも優れているアルゴリズムでないことはわかってます?
もちろん速度が最重視される分野ならばそれで良いことも多いのですが。

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

509 :デフォルトの名無しさん:02/12/15 19:42
素数を求めるアルゴリズムだから
素数を最初から知っているというのはおかしいということです。

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

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

510 :デフォルトの名無しさん:02/12/15 19:43
>>508
予め2と3と5の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。

511 :505:02/12/15 19:43
>2と3の倍数を除くアルゴリズムは

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

512 :デフォルトの名無しさん:02/12/15 19:44
>>510
予め2と3と5と7の倍数を除くアルゴリズムの方が速度と記憶容量の両面で優れていますよ。


513 :デフォルトの名無しさん:02/12/15 19:44
>>505
小手先のテクニックを追求して、アルゴリズムに反映させるから、
より速く・優れているアルゴリズムができるのでは?

514 :デフォルトの名無しさん:02/12/15 19:44
>>512
予め2と3と5と7と11の(以下略

515 :デフォルトの名無しさん:02/12/15 19:45
あらかじめ○○の倍数を除くアルゴリズムの中で優れてる奴きぼんぬ
2はともかく大きな数になると取り除くのにも色々方法がでてくる

516 :デフォルトの名無しさん:02/12/15 19:46
>>509
単にユニバーサルかそうでないかの問題。

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

517 :デフォルトの名無しさん:02/12/15 19:46
gifの解凍アルゴリズムを小手先のテクニックで改良したら
新しいアルゴリズムになってライセンス料支払わなくてよくなるかな?

518 :デフォルトの名無しさん:02/12/15 19:48
>>516
2や3,5の倍数を取り除いてもアルゴリズムは同じです。

519 :デフォルトの名無しさん:02/12/15 19:48
予め2と3と5と7と11と13の(以下略


520 :506:02/12/15 19:49
505へのレスっておかしかった。前半だけ読んで勘違いしてたスマソ。

521 :デフォルトの名無しさん:02/12/15 19:49
>>516
2や3や5の倍数を当たり前に取り除けるのは何故ですか?
2や3や5が素数だからですか?
2や3や5が素数であることを求める処理を省いていいんですか?

522 :デフォルトの名無しさん:02/12/15 19:50
>>517
gif が問題になるのは LZW (> LZ78) を使っているから。
従ってLZWさえ使用しなければ問題ない。
しかし、LZWを別のアルゴリズムに置き換えたgifはもはやgifではない。
(一応、LZWを使わずにgifを実装できるが、遅すぎて使いもにならない)

523 :デフォルトの名無しさん:02/12/15 19:50
誰か2,3,5・・・の倍数を取り除くのを自動化できない?
面倒だから作るのいやなんですよw

524 :デフォルトの名無しさん:02/12/15 19:51

http://petitmomo.com/mm/

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

めぐ(^o^)-☆


525 :デフォルトの名無しさん:02/12/15 19:51
>>521
多分>>516のいいたいことは、ユニバーサル性がどこまで重視されるか、の違いだけ。
立場が違えば解が違う。それだけ、だと思う。


526 :デフォルトの名無しさん:02/12/15 19:52
まぁ考え方(素数列挙に対する姿勢?)の違いなわけで。
素の状態からの素数探索を追求する人も
ひたすら爆速素数列挙を目指してる人も
マターリしませうヽ( ´ー`)丿

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

527 :デフォルトの名無しさん:02/12/15 19:52
素数を求めるので無くて、
素数じゃないのを求めてそれを省くとかするアルゴリズムはどう?

528 :デフォルトの名無しさん:02/12/15 19:53
>>527
それがエラトステネスの篩なわけで・・・

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

530 :デフォルトの名無しさん:02/12/15 19:54
>>527
しね

531 :デフォルトの名無しさん:02/12/15 19:55
>>529
人間の知識を与えるアルゴリズムを非ユニバーサルというらしいですね。

532 :デフォルトの名無しさん:02/12/15 20:04
>>517
既にsusie用のgifプラグインとかそうしてる。

533 :  :02/12/15 20:07
>>531 や、人間の知識も自然な派生(アルゴリズムであれ)だと思うので・・・

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

535 :デフォルトの名無しさん:02/12/15 20:20
分割して篩う方法は>>378>>487など。
たしか>>419も分割してた気がするけど…

536 :デフォルトの名無しさん:02/12/15 20:21
× エラトステネスの基本形
○ 分割しないエラトステネスの基本形
でした。

537 :デフォルトの名無しさん:02/12/15 20:28
>>531
人間の知識っていうかこの場合は答えだからなぁ。
答えを入れれば答えを出すのが速いのは当たり前だし。

538 :488:02/12/15 20:29
>>535
オイラのも入れろ!!!

539 :デフォルトの名無しさん:02/12/15 20:32
>>538
分割してないじゃん

540 :デフォルトの名無しさん:02/12/15 20:33
http://idm.s9.xrea.com/factorization/eratosthenes.html

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

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

542 :デフォルトの名無しさん:02/12/15 20:43
>>541
お見事な縦読み

543 :475==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

544 :Delフサギコ ◆A6VzDeLphI :02/12/15 23:39
           _____
   ∧,,∧∩  /
  頒゚Д゚;彡< 除さん、いらんのですかい!
    ,;゙⊃,ジ   \_____
 〜ミ ,,○
    ∪     しらかた。

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

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;
あと、略

545 :デフォルトの名無しさん:02/12/15 23:47
>>543
それではお手並み拝見。

546 :デフォルトの名無しさん:02/12/15 23:51
>>544
任意のnからmまでの範囲の素数を列挙するのに
除算は1回必要ですが、それに対して
>>485が>あぁ、確かに2、3回除算使ってるな>範囲列挙
と書いてるので分かって無いと書いただけで
2・3・5等の素数を、省いて篩う場合には必要です
と言っても、そのコード読めないので
そのコードが正しいかは分かりませんが…

547 :485:02/12/15 23:57
>>543
うひぃ、怒られた。
適当なコト言ってすまぬ。>>543の言うとおりです。

でも487は俺じゃないよ…

548 :デフォルトの名無しさん:02/12/16 00:12
>>544
分からないと言いつつも分かったかも…
前の3を省いた時に使ってたnと2nを交互に足してった奴を
7までの素数に拡大したバージョンですね
それは、最初の一回は必ず除算を使いますし、省けませんね…

549 :Delフサギコ ◆A6VzDeLphI :02/12/16 00:20

キュピィィィン   +   /
     ∧,,∧   < よくわかりますた
    ミ,, ゚Д゚ミ .  \>>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まで
篩いに落ちるのを、目で見てソースに落とすのを
考えると鬱るので、まだやってません。

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

551 :デフォルトの名無しさん:02/12/16 02:12
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;}}

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

553 :デフォルトの名無しさん:02/12/16 09:03
>>544
それは、その部分を関数にして処理しようとするからそうなるんで、
高速化したいなら配列 を作って状態遷移型に処理させるといい

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

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

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

けど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までは苦でなさそう。


555 :デフォルトの名無しさん:02/12/16 10:49
まあ今のパソコンのCPUだと除算も1クロックな時代だから必要ないけど
一昔前は >>554の通り 除算は遅かった。

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

556 :デフォルトの名無しさん:02/12/16 17:46
>>553
nまでの素数を求めたい時に必要な素数は√nまでの素数p
それらの各素数pがマークを付け始めるべき位置はp*p
だから、その最初の位置を決める時にp/2310の除(余)算が必要なんだって

557 :デフォルトの名無しさん:02/12/16 20:37

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

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

561 :デフォルトの名無しさん:02/12/16 20:45
途中まで(100ぐらい)しか見てないから
正しいと思うが間違ってたらスマソ

562 :デフォルトの名無しさん:02/12/16 21:16
一億やるのに13秒(Pen4 1.7G・出力なし)
ただバグがあって、でかい数(2^32 -1)までやるとうまくできない?とか・・

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

563 :アフォ学生 ◆ZrbomZ0t3. :02/12/16 22:02
誰もレスくれないのかYO!
さびしいよ〜〜

さびしいからトリップ付けましたw
もしかして激しくガイシュツ?
そいつはスマソ

564 :548==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'に保存
のように、分割した方が、篩いも圧縮も早くなります
(もちろん分割した事によるロスも馬鹿には出来ませんが)
と言う訳で、長くなりましたが、頑張って下さい

565 :デフォルトの名無しさん:02/12/17 18:19
自動化でたね・・・
しかも早いし

566 :デフォルトの名無しさん:02/12/17 20:20
削除依頼が出てた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
よくわからんタイミングで削除依頼が出てるな

568 :デフォルトの名無しさん:02/12/17 23:51
>>565
一億やるのに13秒で早いだと?
これが、こんなに遅いのはjavaを使ってるからでも無ければ
テーブルを自動化したからでも無い
chkSosuu()で、除算で素数判定してるからだ
もう少しコードを読んでから、早い遅いを語ってくれ

569 :デフォルトの名無しさん:02/12/18 02:29
喧嘩腰になるなってば

570 :568:02/12/18 06:32
>>569
スマソ

571 :デフォルトの名無しさん:02/12/18 22:39
C++で324のコードを走らせる場合、必要なヘッダファイルは何かいな?
あほな質問でごめんちゃい。

572 :デフォルトの名無しさん:02/12/18 22:44
>>571
#include <stdio.h>
#include <stdlib.h>
#include <malloc..h>
多分。

573 :571:02/12/18 23:02
>>572
stdbilを読み込めないと言ってくる・・・泣
>他の人
スレ違いでごめん。

574 :571:02/12/18 23:06
またごめん・・・
573は無視して・・・。

575 :デフォルトの名無しさん:02/12/18 23:14
stdbil

なんだそれは食い物か

576 :デフォルトの名無しさん:02/12/18 23:23
世界標準ビルゲイシだろ!まったくM$オタクのくせしてそんなことにも気づかない(ry

577 :デフォルトの名無しさん:02/12/21 13:35
保守

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

579 :デフォルトの名無しさん:02/12/23 00:36
>>578
頑張りましたね…
でも、出来れば少しだけでもコメントをつけるなり
影響の少ない範囲で、main()のコードを複数の関数に分割して欲しかった…

580 :デフォルトの名無しさん:02/12/23 03:28
力業って言葉がよく似合うコードだと思った。

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

582 :578:02/12/23 17:36
3、5、7 じゃなくて 2、3、5 でした。

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


584 :578: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は例外)ことを
利用しているようなのですが、そういう方法もあるみたいですね。

585 :デフォルトの名無しさん:02/12/25 18:30
へえ・・・
 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)ガーン

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

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

588 :デフォルトの名無しさん:02/12/28 18:17
素数マップを作る為にキャッシュに収まらないサイズの
メモリアクセスを行ってるから、配列を使うとそれだけ
キャッシュミスが増えるって事じゃないのかな

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


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

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

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

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

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

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

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

593 :デフォルトの名無しさん:03/01/02 01:58
>>592
がんがってくだちい。自分は>>590を試してみようと思ふ

594 :デフォルトの名無しさん:03/01/02 20:26
すまんが、>>578のリンク先からアクセス拒否をくらうんだけど。。

595 :デフォルトの名無しさん:03/01/02 20:42
>>594
会員専用?

596 :デフォルトの名無しさん:03/01/02 20:57
で、結局何桁までもとまったの?

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

598 :597: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くらいまでの素数は見つかっているみたいですね。果てしない。

599 :デフォルトの名無しさん:03/01/04 01:04
ちょびっと横道にそれるのですが、
1Gh 256Mb で1時間かけてあるふたつの素数の積を
素因数分解をする場合には何桁の素因数分解ができれば優秀なプログラムと言えるのでしょうか?

600 :デフォルトの名無しさん:03/01/04 07:40
>>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が素因数分解出来れば非常に優秀

601 :デフォルトの名無しさん:03/01/04 11:10
600さんレスサンクスです
64bitですかぁ 簡単にはいきそうにないっす。
気長にちびちびとやっていきます。
完成すればうpするのでまっててちょ。

602 :597: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だとこれが限界かなぁ。。。
みなさんはどうです?


604 :603:03/01/04 21:56
追加

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

605 :デフォルトの名無しさん:03/01/04 21:58
>>603-604
環境示せ。過去ログにVBの事も出てたよ。

606 :603:03/01/04 22:03
Pentium(r)V processor GenuineIntel ~800Mhz

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

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

607 :デフォルトの名無しさん:03/01/04 22:15
ん?>>441のは出力ありだろ?

608 :デフォルトの名無しさん:03/01/04 22:17
>>607
ボタンをチェックすれば出力無しに出来るよ。

609 :デフォルトの名無しさん:03/01/04 22:23
>>608
それでもTEMPフォルダに出力してるようだが

610 :603:03/01/04 22:32
>>609
本当だ・・・ビックリ・・・・。
もっと修行せねば。
ありがとう!

611 :デフォルトの名無しさん:03/01/04 22:38
>>610
がんがってね。応援するよ

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

613 :597:03/01/06 12:38
10兆まで計算するのにAthlonXP1800で21時間もかかった...

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

615 :デフォルトの名無しさん:03/01/07 06:18
>>597
djb氏って、それって何処にあるの?

616 :pascal:03/01/07 10:53
とりあえず昔同じことやったファイルがCD-Rにあった。計1G。
2^31 未満の素数の全リスト。
適当に作ったやつだから2日くらいかかったけど。(Pen!!! 1.00GHz)

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

ソース発掘中・・・。

#それとは別に10万個ずつ素数を見つけてファイルに書き込むものもあり。
#ともに暇ならUPしますが。

617 :デフォルトの名無しさん:03/01/07 11:22
>>615
http://cr.yp.to/djb.html
ここの primegen ってとこです。

618 :デフォルトの名無しさん:03/01/07 11:59
>>616
うpきぼーん

619 :pascal:03/01/07 13:57
>>618
発掘・実行してみたらとてつもなく遅かったので自主規制です(^-^;
てか恥ずかしくて見せられん。
ふるいも使わずビット演算とかもせず、ゆえに割り算ばっかりしてるので1000万までで10秒弱かかります。。。
似たことやってる人がいてちょっとほっとしました(^-^)

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

駄文+横道+長レスすまそ。

620 :デフォルトの名無しさん:03/01/08 09:57
そもそも円周率とは何か?
3.14
というのは円周率の定義でないと最近おもいつきはじめている。

621 :デフォルトの名無しさん:03/01/08 12:09
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氏のは謎なのでそこに希望があるかもしれません。

622 :615:03/01/08 17:05
>>597
サンスクコ
コンパイル出来ませんが
そのうち、コードだけ読んでみます

623 :デフォルトの名無しさん:03/01/08 19:28
>>620
頭大丈夫?

624 :621:03/01/08 20:18
print_primeの引数はuint64の間違いです。
だから速かったみたいです。djb氏のとは比較にならないくらい遅いです。
32ビットの範囲でも long int と long long int では割り算の速さが全然違いますね。

625 :620:03/01/08 23:16
>>623
円周率の定義教えてよマジで

626 :デフォルトの名無しさん:03/01/09 01:00
>>625
小学校で習わなかったの?

627 :デフォルトの名無しさん:03/01/09 03:30
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
   いずれは。

628 :デフォルトの名無しさん:03/01/09 04:12
2ちゃんねる が衰退していく

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

http://ascii24.com/news/reading/causebooks/2002/07/01/636911-000.html


629 :デフォルトの名無しさん:03/01/09 13:17
>>625
円の面積÷半径の2乗

630 :デフォルトの名無しさん:03/01/09 13:42
節穴ないスレは落書き>無視
節穴はマジ書き>通報
ってルール駄目?

警察忙しくなりそうだな。

631 :デフォルトの名無しさん:03/01/09 14:48
いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう

632 :625:03/01/09 16:03
>>626
小のころは遊んでばっかりで、勉強しなかったから。
>>629
S=πr^2

π=S/r^2
に変形してもいまいちπの正体が見えないな。


633 :デフォルトの名無しさん:03/01/09 16:42
「円周を直径で割った数」でいいじゃん

つーか検索しろよ

634 :デフォルトの名無しさん:03/01/09 17:34
======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
────────────────────────────

635 :デフォルトの名無しさん:03/01/09 19:04
>>633
それが算数の授業での説明なわけね。
2chねらーに聞きたかったんだよう。

636 :デフォルトの名無しさん:03/01/09 21:30
>>635
半径1の円を内接、外接する3角形で近似する。
極限をとれば、同じ値に収束して、その値が円周率。

637 :デフォルトの名無しさん:03/01/09 22:27
>>635 「円周率って何?」と聞かれたら、やっぱり定義を答えるだろう。2ちゃんねらーでも。
だったら>>633が正解。

ム板的に、円周率の近似計算アルゴリズムを聞きたいなら別だけど。

638 :デフォルトの名無しさん:03/01/09 23:23
>>743 盛り上がるのは結構だが、pc系の荒らしにはもう疲れましたよ(;´Д`)


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

639 :デフォルトの名無しさん:03/01/10 09:47
OK.

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

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

「早急に」+、前向きに
色々と検討して下さいますでしょうか。
私は18歳です。其方のプロフィールを簡単に今お願いします!ありがとう。

640 :デフォルトの名無しさん:03/01/10 10:27
んじゃ俺今からけんすうにワン切りしよ(^_^;)


641 :デフォルトの名無しさん:03/01/10 11:00
ついさっきNHKFMの2時のニュースで2ちゃんのこと言ってたぞ。

642 :デフォルトの名無しさん:03/01/10 11:44
誹謗中傷と認識 ← ここの基準をしっかりしなくてはならない。
          削除人の個人個人の判断じゃだめ。


643 :デフォルトの名無しさん:03/01/10 12:14
他が危険で、にちゃんも危険になったとでも〜
の間違いだと思われ。
IP取ってない方が珍しいし。

644 :デフォルトの名無しさん:03/01/10 12:15
すれ違いサぁ

645 :デフォルトの名無しさん:03/01/10 12:37
ヾ( ゚д゚)ノ゛シナチクー

646 :デフォルトの名無しさん:03/01/10 14:59
某、毒見要員だったのでござるか|/゚U゚|

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

647 :デフォルトの名無しさん:03/01/10 16:27
大阪キタ━━━━━━(゚∀゚)━━━━━━ !!!!!

648 :デフォルトの名無しさん:03/01/10 21:14



注意:ここは素数列挙アルゴリズムスレです


649 :デフォルトの名無しさん:03/01/10 22:51
2003年1月10日がおいらの青春の1ページに記録されますた。

650 :デフォルトの名無しさん:03/01/10 22:57
なんかこれ見よがしに必死に他の掲示板へ誘導してる香具師が居るように見えるんだがw

651 :デフォルトの名無しさん:03/01/11 00:13
おまいら、これ見れ!
http://dailynews.yahoo.co.jp/fc/computer/2channel/

652 :デフォルトの名無しさん:03/01/11 00:22
えっと、無知で突っ込みを入れられるのを覚悟で。。

IPの記録が抑止にもなるなら、削除系の板のリモホ表示をやめて
みるのはどうでしょう。
依頼者のホストを削除板以外の板に晒されることもないでしょうし。

653 :デフォルトの名無しさん:03/01/11 09:46
「氏ね」だとかはいいよね?
管理人は「逝ってよし」もダメだと言うのか!?

654 :デフォルトの名無しさん:03/01/11 09:49
P2P専用掲示板zigmoを再開発していると作者が言っているが。。。

655 :デフォルトの名無しさん:03/01/11 10:21
======2==C==H======================================================

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

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

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

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

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

んじゃ!

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

656 :デフォルトの名無しさん:03/01/11 11:15
ちくり板つまらなくなりそなヨカン

657 :デフォルトの名無しさん:03/01/11 11:45
無線LANでNYBBSをやるのが好ましいのでしょうか?

658 :デフォルトの名無しさん:03/01/11 12:47
内部告発やったら自分がただですむわけナイヨ

659 :デフォルトの名無しさん:03/01/11 12:50
>658
復讐的なチクリもなくなるのだぞ!!

660 :デフォルトの名無しさん:03/01/11 13:16
何が実験だよ
IPなんか始めから記録してるだろよ

661 :デフォルトの名無しさん:03/01/11 15:44
逆に立てて欲しくなかったんだが(w

662 :デフォルトの名無しさん:03/01/11 23:46
半角板がおもしろい

663 :デフォルトの名無しさん:03/01/11 23:56
2chで告知するかどうかを知ることで?(^_^;)なんでそうなるんだ?

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

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

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

なるほど(^_^;)

664 :デフォルトの名無しさん:03/01/12 02:36
あきらめる(・∀・)

665 :デフォルトの名無しさん:03/01/12 02:41
中部地区では一週遅れで今の時間にやってる。でも悔しくないのが種の良いところだな

666 :デフォルトの名無しさん:03/01/12 05:02
>>665
誤爆?
少女漫画かアニメ板から

667 :デフォルトの名無しさん:03/01/12 10:07
祭り開催中!!!
メンヘルと言ってた女が実はシャブ中だった!!!
http://tmp.2ch.net/test/read.cgi/tubo/1042129878/l50

668 :デフォルトの名無しさん:03/01/12 10:10
博之は寝た。

669 :デフォルトの名無しさん:03/01/12 20:53
やっぱりな・・・・

670 :デフォルトの名無しさん:03/01/12 20:56
>スパーハカーにIPから本人のメアドを割り出してもらう
Hackerの名を汚すな。馬鹿。
IPからメールアドレスだと?
馬鹿か。割り出せるのは契約者の接続アカウントだ


671 :デフォルトの名無しさん:03/01/12 21:06
書き込めた!  倉庫板さんオツ!感謝!

672 : :03/01/13 18:24
test

673 :山崎渉:03/01/13 18:43
(^^)

674 :デフォルトの名無しさん:03/01/13 22:08
つまんね

675 :山崎渉:03/01/15 17:50
(^^)

676 :山崎渉:03/01/23 22:23
(^^)

677 :デフォルトの名無しさん:03/01/27 00:04
何で荒れてるんだ???

193 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)