こんな事をしている場合では無いのですが・・・気持ちを落ち着かせたいのかもしれません。
ちょっと前から、 プロジェクト・オイラー というサイトにあるプログラミングの課題をやっています。このブログを確認したら、3 か月ちょっと前、 6 月 9 日 でした。
リハビリのためにやっていますが、亀の歩みでちょっとずつ進めています。
現在、 10 問目 に取り組んでいます。
「素数の和 (Summation of primes)」という問題です。
10 以下の素数の和は 2 + 3 + 5 + 7 = 17 である。
2000000 以下のすべての素数の和を求めよ。
最初に考えた解き方は、2 から始めてそれぞれの数が素数かどうかを判定し素数ならば足していく、これを 2000000 まで繰り返すという方法です。それぞれの数に対する素数の判定は、その数未満の数 (実際にはその数の平方根未満の数) でその数が割り切れるかどうかを順に調べていき、どこかの時点で割り切れれば素数ではない、調べたすべての数で割り切れなければ素数とする、という方法を使います。この方法は試し割り法とも呼ばれ、単純ですが有用な方法です。
次に考えた解き方がエラトステネスの篩による方法です。上の方法でコードを書いている最中に思い出しました。
有名なアルゴリズムなので学生の時から何となく知っていたのですが、実際にプログラムとして実装したのは会社に入ってからでした。C 言語の練習問題の一つとしてこの課題がありました。
ご存知の方はたくさんいらっしゃると思いますが、自分の理解のために簡単に紹介しておきます。
エラトステネスの篩は、与えられた正の整数 N 以下の素数の列を求めるアルゴリズムです。
N = 10 の場合、得られる素数の列は 2, 3, 5, 7 です。
N = 20 の場合、得られる素数の列は 2, 3, 5, 7, 11, 13, 17, 19 です。
一般的な正の整数 N に対しては次のようになります。
(1) L を数列 2, 3, 4, 5,..., N とします。この段階では L の先頭要素は 2 です。
(2) L の先頭要素を p とおきます。
(3) L から p 以外のすべての p の倍数を取り除き、残った要素からなる数列をあらためて L とします。また、新しい L における p より大きい最初の要素のをあらためて p とします。この手順を、 p が N の平方根以上になるまで繰り返します。
(4) 上記の (3) の手順が終了した時の L が求める素数の列です。
たとえば、 N = 20 の場合、手順を進めるに連れて L と p は次のように変わっていきます。
L : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
p : 2
L : 2, 3, 5, 7, 9, 11, 13, 15, 17, 19
p : 3
L : 2, 3, 5, 7, 11, 13, 17, 19
p : 5 †
† 5 は N = 20 の平方根 4.47213... よりも大きいのでここで終了です。
この方法を使ってプロジェクト・オイラーの第 10 問を解くには、求まった素数の列 L のすべての要素を足し合わせればよいことになります。
C 言語で試し割り法、エラトステネスの篩、各々を使ったプログラムを書いて実行させました。エラトステネスの篩を使った処理は非常に速いですね。このあたりはソースコードを合わせて後で追記しておこうかと思います。
小さな例ですが、アルゴリズムというのは面白いものです。
新品価格
￥386 から
(2014/9/16 20:22時点)
【このカテゴリーの最新記事】
- no image
- no image
- no image
- no image
- no image
