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

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

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

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)