エラトステネスの篩

#77 エラトステネスの篩

今回もProject Euler on F#ネタで押してみます。
まぁ、トピックに取り上げるのは今回が最後、またはしばらくお休みにするとは思いますf^_^;

今回挑戦したのは第3問。

Problem 3 - Project Euler

以下は問題の引用です。
13195 の素因数は 5、7、13、29 である。

600851475143 の素因数のうち最大のものを求めよ。

ここで、まずは素数リストを作ることにしました。
これだけ大きな数の素因数なので、処理性能も意識したかったことと、前回の轍を踏まないように、作成しているリストの要素を元に新しい要素を追加する方法を考えました。

なお一般に、コードを書き始める時に性能に拘るのは、処理の見通しを悪くしたり、余計に性能を悪くしたり、良くないとされています(`・ω・´)
ただ、再帰や同じ処理を行うところで、前の結果を使わず1から繰り返すようなコードを書いていたら、リソースを食いつぶして仕方がないのです。
これは失敗を糧にしたもの、と考えてください。


さて、書き上げたの素数リストを求める関数が次のコードです。
let Sieve n =
    if n > 1
        then
            let rec eratMain ls n i =
                if i <= n
                    then
                        if List.exists (fun x -> (i % x) = 0) ls
                            then eratMain ls n (i+1)
                            else eratMain (ls @ [i]) n (i+1)
                    else ls
            in eratMain [2] n 2
        else [0]
これが正しく動くか、簡単なテストをしてみます。
> let pLs = Sieve 100;;

val pLs : int list =
  [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]
>
次のWikipediaのページの結果と一致していますね。

エラトステネスの篩 - Wikipedia

次は、この素数リストを使って、600851475143 という大きな数の素因数を求めてみます。

続きを読む »

プロフィール
あわせて読みたい
あわせて読みたい
記事検索
Project Euler
なかのひと
アクセス解析
Coderwall
  • ライブドアブログ

トップに戻る