1001コメント344KB

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

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

00011

NGNG

メモリとかも考慮に入れた超高速なアルゴリズムを真剣に考えるスレ

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

NGNG

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

0154 ◆DhJkQxJw

NGNG

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

0155 ◆DhJkQxJw

NGNG

# >>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に移植してみたのれす。。
# でも・・・・・遅いっすね★

0156デフォルトの名無しさん

NGNG

>>◆DhJkQxJw
俺はRubyのコトはよく分からんのだが過去レスに色々ソースがあるから
見てみ（大概Cだけど）。

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

0157 ◆DhJkQxJw

NGNG

･ﾟ･(ﾉД`)･ﾟ･ｳﾜｰﾝ
漏れの活躍してた素数スレが消えちゃったよ～★

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

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

0158デフォルトの名無しさん

NGNG

>>157
しばらくすると消えるから必要なレスをコピペして。
http://pc3.2ch.net/test/read.cgi/pc3tr/1030500162/

0159デフォルトの名無しさん

NGNG

正直、どこをどう読めば活躍してるのか分からない。
頑張って勉強していたスレ、というなら認めるが。
活躍というなら、>>126を超えてくれ。

0160 ◆DhJkQxJw

NGNG

>>158
うひひ☆サンクスれす☆

>>159
ごめそね★
「暗躍」って言い換えればいいれすか？

0161 ◆DhJkQxJw

NGNG

ちなみに、漏れが自力で作った最速コードは
これ↓れした。いかな厨房でも理解できそうれす。

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

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

これでも>>152-155よりは早いのれす。
求めた素数をすべて配列に保持するアルゴリズムを
実装すると、かえって速度が落ちるようなのれす。
うひひ。

0162デフォルトの名無しさん

NGNG

>>160
無駄レスするな。暗躍の意味をわかっているのか小一時間。

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

0163 ◆DhJkQxJw

NGNG

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

0164デフォルトの名無しさん

NGNG

こんな奴が俺より年上なのか、情けない。

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

0165 ◆DhJkQxJw

NGNG

>>164
うひひ★どうせ漏れはﾄﾞｷｭｿれすよ★
ﾄﾞｷｭｿはﾄﾞｷｭｿらしくしてるのが
一番なのれすよ★
ﾊｧｧ･･･

0166デフォルトの名無しさん

NGNG

>>165
お前が酒を飲むなんぞ10年早いわ。
だいたい >>126 のruby版は既にあるし。

0167 ◆DhJkQxJw

NGNG

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

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

0168デフォルトの名無しさん

NGNG

>>167 試合放棄？
そうか、ここまでよく頑張ったな。いいよ。

0169 ◆DhJkQxJw

NGNG

･ﾟ･(ﾉД`)･ﾟ･ｳﾜｰﾝ
いぢめっこがいるよ～★

　　　　　　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　　　　　　｜も.｜
　　　　　　　　　　　　　　　　　｜う　|
　　　　　　　　　　　　　　　　　│来│
　　　　　　　　　　　　　　　　　│ね│
　　　　　　　　　　　　　　　　　│え .|
　　　　　　　　　　　　　　　　　│よ .|
　　　　　　ﾊﾞｶ　　　　ｺﾞﾙｧ　　│ !!.│
　　　　　　　　　　　　　　　　　└─┤　　　　ﾌﾟﾝﾌﾟﾝ
　　　　ヽ(`Д´)ﾉ　ヽ(`Д´)ﾉ　　(`Д´)ﾉ　　　（　`Д）
　　　　|￣￣￣|─|￣￣￣|─|￣￣￣|─□（ヽ┐U
～～　￣◎￣　　.￣◎￣　　￣◎￣　　 ◎－>┘◎

0170 ◆MAKNgZ1Q

NGNG

はじめまして～☆
こんばんわ～☆

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

0171デフォルトの名無しさん

NGNG

面白くない。

0172デフォルトの名無しさん

NGNG

保守

0173デフォルトの名無しさん

NGNG

>>172
ていうか、sageてない？

0174デフォルトの名無しさん

NGNG

>>173
sageのまま保守することがいけないことか？

0175デフォルトの名無しさん

NGNG

>>174
禿同！！

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

0176デフォルトの名無しさん

NGNG

>>175
そういいながらageて書く君が好きだ

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

0177デフォルトの名無しさん

NGNG

>>176
やってみれば。
小手先の技でも塵も積もれば山となる…かも

0178デフォルトの名無しさん

NGNG

そうだな

0179DQN.cc

NGNG

そうれすね

0180デフォルトの名無しさん

NGNG

俺付属の脳ｺﾝを使うと
A>list　素数
1、2、3，5、7、11、13、17、19、23、26、29、31、37とでてくる。
A>

0181デフォルトの名無しさん

NGNG

>>180
馬鹿31は素数じゃねぇよ

0182デフォルトの名無しさん

NGNG

>>181
馬鹿はあんただよ…

0183デフォルトの名無しさん

NGNG

おばかさん１は素数じゃねぇよ

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

0184デフォルトの名無しさん

NGNG

8　*　9＝31
は　　く　さい
白菜

0185デフォルトの名無しさん

NGNG

めっちゃ素直にふるいを実装。
% time ./era 10000000 78497
prime[78497] is 999983
3.560u 0.390s 0:04.16 94.9% 0+0k 0+0io 0pf+0w
G４450Mhz でこのくらい。
「./era」がバイナリ。
最初の引数が、ふるいの大きさ。
次の引数で、いくつめの素数を表示するかを指定( チェック用 )

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

0186デフォルトの名無しさん

NGNG

>>185 頑張ってくれ。俺はこれといった面白いアイデアが無い。

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

0187DQN.cc

NGNG

>>185
改造したらソースきぼ～ん☆

0188デフォルトの名無しさん

NGNG

ソースがいっぱい

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

0189デフォルトの名無しさん

NGNG

>>188
数はあるけど…

0190188

NGNG

まぁ、プログラミングの練習の段階ですから

0191185

NGNG

"直感的な素数の倍数を飛ばす[ふるい]”を実装してみました。
% time ./sieve 10000000 5
prime[664578] -> 9999991
1.940u 0.400s 0:02.55 91.7% 0+0k 0+0io 0pf+0w ( G4 450MHz )
ちょっとだけ、早くなりました。
ちなみに、最初の引数がふるいの大きさ。
二つ目の引数が、"直感的な素数"の最大値。
なぜか、5のときが、最速でした。
# この値を大きくすると、どんどん早くなるはずだったんだけどな。

ソース upしたいけど、253行にもなっちゃった。

0192デフォルトの名無しさん

NGNG

あぷろだにうｐ！

0193デフォルトの名無しさん

NGNG

数が大きくなればなるほど素数の出現頻度は低くなるの？

0194デフォルトの名無しさん

NGNG

>>191
凄く厨な事聞いてるみたいで恥ずかしいのだが、
＞1.940u 0.400s 0:02.55 91.7% 0+0k 0+0io 0pf+0w ( G4 450MHz )
これの読み方がわからぬ(；´Д`)
何が何を表してるのか教えてくだされ。。

0195185

NGNG

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

0196デフォルトの名無しさん

NGNG

>>193
π(x)～x/log(x)なんだそうな。
だからちょっとずつ頻度は低くなる。

0197デフォルトの名無しさん

NGNG

>>195
ファイルが見つかりません…

0198デフォルトの名無しさん

NGNG

http://tool-ya.ddo.jp/2ch/trash-box/file/20020913081215032.gz
これはどなた？

0199185

NGNG

>>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っぽいので、
この部分が短くなるように努力してます。

0200デフォルトの名無しさん

NGNG

200 get!っと

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

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

0201185

NGNG

>>200
っていうか、漏れｱﾌｫなので、
一個のメソッドが30行くらいを越えると、
全然理解できなくなっちゃうのです。

0202デフォルトの名無しさん

NGNG

誰かmainにまとめたバージョンうｐきぼんぬ

0203デフォルトの名無しさん

NGNG

age

0204デフォルトの名無しさん

NGNG

>>202
七行スレに依頼しる！

0205デフォルトの名無しさん

NGNG

>>204
見づらさが500％増加の見込み

0206ソースを読まずにカキコ

NGNG

出入りの激しいループの奥深くの関数以外は速度面から見てもベタ書き不要。
コンパイラによってはinline指定子もあるし。

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

0207デフォルトの名無しさん

NGNG

>>206 正論だな

0208デフォルトの名無しさん

NGNG

素数なんて列挙してどうするの？

0209デフォルトの名無しさん

NGNG

>>201
30行？カスだな。

0210デフォルトの名無しさん

NGNG

>>208 より速く、より高く、より遠くへ。男のロマソだ。

0211デフォルトの名無しさん

NGNG

>>210 同意
シンプルな問題ではあるが、奥が深い
素数自体がおもしろい数だし

0212デフォルトの名無しさん

NGNG

>>208
賞金もらえるぞ

0213デフォルトの名無しさん

NGNG

そこに素数が（可算個）あるからだ。

0214デフォルトの名無しさん

NGNG

hoshu

0215デフォルトの名無しさん

NGNG

限界目指してます

0216デフォルトの名無しさん

NGNG

ほっしゅ

0217デフォルトの名無しさん

NGNG

列挙ってことは、配列かなんかに
素数を全部入れなきゃ駄目？

0218デフォルトの名無しさん

NGNG

>>217 標準出力とかに順番にヌケも間違いも無く出せればそれでいいと思うよ。

0219デフォルトの名無しさん

NGNG

>>217
速さを目指すなら、バイナリでファイルに出力することを推奨

0220デフォルトの名無しさん

NGNG

最後は可読な状態で出力がいいな。
バイナリだと何でもありになりそうだから…

0221デフォルトの名無しさん

NGNG

>>220
出力0.0001秒、表示200時間とか？

0222デフォルトの名無しさん

NGNG

んなのがあるかい

0223デフォルトの名無しさん

NGNG

>>220
そうだな。
じゃあテキストで、tab 又は改行で区切るってことで。

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

0224デフォルトの名無しさん

NGNG

素数なんか列挙して何になるの？

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

0225デフォルトの名無しさん

NGNG

>>224
禿しく慨出。

0226デフォルトの名無しさん

NGNG

>>224
数学は列挙したりなどしない。定義さえすれば、そこにあるものだから。
そして利用する場合には、プログラム的なアクセスが必要になる。

0227デフォルトの名無しさん

NGNG

板違い。

0228デフォルトの名無しさん

NGNG

数学とプログラム、特にアルゴリズムは深い関係があるのを知らないのかい

0229デフォルトの名無しさん

NGNG

素数列挙列挙ではあんまり数学的なテクニックが使えないからねえ。

0230デフォルトの名無しさん

NGNG

素数列挙って言うと、
1:エラトステネスの篩
2:順番に素数判定
の二つしか知らないのだけど、もっと素敵な列挙法ってないでしょうか？

0231デフォルトの名無しさん

NGNG

>>230
素数データベースから読み出して表示
（列挙は列挙でしょ♪）

0232デフォルトの名無しさん

NGNG

enumerate of prime numbers.

0233デフォルトの名無しさん

NGNG

適当な奇数を表示して問いかける。

0234デフォルトの名無しさん

NGNG

>>233
意味が良くわかんないんだけど。
説明していただけるかしら？

0235名無しさん ◆jZGaCDQNcc

NGNG

>>234

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

0236デフォルトの名無しさん

NGNG

それは、>>230の2に該当ということでいいのか

0237デフォルトの名無しさん

NGNG

結局エラトステネスが一番素敵だと思う。
プラス2の倍数を飛ばしてみたり。

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

0238名無しさん ◆jZGaCDQNcc

NGNG

>>237
「2の倍数」って・・・。

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

0239デフォルトの名無しさん

NGNG

>>237 胴衣

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

0240デフォルトの名無しさん

NGNG

あと如何にメモリの使用量を抑えるかですな

0241デフォルトの名無しさん

NGNG

数学板より
http://science.2ch.net/test/read.cgi/math/1033486518/
http://science.2ch.net/test/read.cgi/math/1030077269/

0242デフォルトの名無しさん

NGNG

>>237
無限に存在する素数を相手にする時に限界があるよね。
2の倍数、3の倍数の枝刈りのようなもの。

0243デフォルトの名無しさん

NGNG

>>242
俺たちにゃ有限の時間しか残されていないのだから、有限でいいのさ

0244デフォルトの名無しさん

NGNG

ピタゴラス数を列挙(・∀・)ｼﾖｰﾖ
a²+b²=c²な数を！

0245デフォルトの名無しさん

NGNG

[{3,4},{5}]

0246デフォルトの名無しさん

NGNG

bracket brace three comma four brace comma brace five brace bracket

0247デフォルトの名無しさん

NGNG

>>244
それセンター試験でやった。懐かすぃ

0248デフォルトの名無しさん

NGNG

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

0249名無しさん ◆jZGaCDQNcc

NGNG

>>248
どのコードよ？

0250248

NGNG

書き込もうと思ったが、長過ぎたようだった。

0251248

NGNG

#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 という名前で。

0252248

NGNG

#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 。

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