«

»

2月 25

エラトステネスのふるい

素数を求める有名なアルゴリズムのエラトステネスのふるいを試してみました。

エラトステネスの篩 -Wikipedia

ステップ 1

整数を最初の素数である 2 から昇順で探索リストに羅列する。

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

ステップ 2

リストの先頭の数を素数リストに記録する。

素数リスト:2
探索リスト:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

ステップ 3

前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。

素数リスト:2
探索リスト:3 5 7 9 11 13 15 17 19

ステップ 4

探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る。

19 は 2 の平方よりも大きいので、ステップ 2 に戻る。
ステップ 2

素数リスト:2 3
探索リスト:3 5 7 9 11 13 15 17 19
ステップ 3

素数リスト:2 3
探索リスト:5 7 11 13 17 19
ステップ 4

19 は 3 の平方よりも大きいので、ステップ 2 に戻る。
ステップ 2

素数リスト:2 3 5
探索リスト:5 7 11 13 17 19
ステップ 3

素数リスト:2 3 5
探索リスト:7 11 13 17 19
ステップ 4

19 は 5 の平方よりも小さいので、リストに残っている数が素数である。

結果:2 から 20 までの数に含まれる素数は、

2 3 5 7 11 13 17 19

となる。

とりあえずまずはコードを書きます。

#coding:utf-8

#素数の最大数
max_prime = 100000

#探索リスト作成
search_list = range(2,max_prime+1)

#素数リスト
prime_list = [0,]

while max(prime_list)*max(prime_list)<max(search_list):
    prime_num = search_list[0]
    search_list.remove(prime_num)
    prime_list.append(prime_num)

    for num in search_list:
        if num%prime_num==0:
            search_list.remove(num)

prime_list = prime_list+search_list
print prime_list

とりあえずパッと思いついたのはこんなかんじです。最初、search_listに残ったものを結合するのを忘れて手間取りました。

正直、遅いですw 1万だと0.5秒くらい(CPU利用率30%)ですが、なぜかその10倍の10万にすると1分近くかかります。優先度? nice値を修正すればどうにかならなくもない気もしないでもないです。

まぁ、append()とかdelete()とかを使っていたり、さらにいちいちforでsearch_listを一覧しているのも気になります。

lga128@PC-8:~/python/prime$ python primetest1.py
[0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

こんな感じ。

最近世界樹の迷宮IIIをまたやってます。いや、いいですねぇ。

Pythonが自分に合いすぎててJSがあまり覚えられないです。。 最初に選ぶ言語をPythonにしておいて本当に良かったです。直感的に文法がわかります。

テスト一週間前。。w

Permanent link to this article: http://lga128.nekobaka.net/2012/02/prime/

2 comments

  1. 松本海月

    俺もこういう数学的なプログラムを作ろうとしていたところでエ…なんとかのふるいを使ったプログラムを作られちゃいました。

    いえ、素数とは関係のない分野なので良いのですがw

    JSは他の言語より複雑な感じがします。
    まあjQueryとか実装する機会もあるでしょうし本当は是非押さえておきたいのですがね。

    テスト1日前。。w

    1. okanakkun

      JSはC言語っぽいよね。jQueryとかでWebデザインもできるようになりたい。
      テスト1日前ってww おいおいww

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次の HTMLタグおよび属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Time limit is exhausted. Please reload the CAPTCHA.