1

これはプロジェクト オイラーの問題です。

N 以下のすべての素数を一覧表示する Fastest way から学び 、clojure を実装しました。

(defn get-primes [n]
  (loop [numbers (set (range 2 n))
         primes []]
    (let [item (first numbers)]
      (cond 
        (empty? numbers)
        primes
        :else
        (recur (clojure.set/difference numbers (set (range item n item)))
               (conj primes item))))))

次のように使用されます。

(reduce + (get-primes 2000000))

しかし、それはとても遅い..

なぜだろう、誰かが私を啓発できますか?

4

1 に答える 1

3

このアルゴリズムは正確でさえありません: 最後の反復を除く各反復で(first numbers)、その時点での の値を に追加しますprimesが、使用中の集合データ構造が順序付けされていないため、実際に素数であるという保証はありません。(これは、リンク先の質問の編集で作成者が言及したように、Python のオリジナルにも当てはまります。) したがって、最初(set (range ...))(into (sorted-set) (range ...)).

それでも、これは素数を見つけるための優れたアルゴリズムではありません。より良い結果を得るには、Java 配列と/を使用してエラトステネスのふるいの命令型実装を作成するか、Melissa E. O'Neill の美しい論文The Genuine Sieve of Eratosthenes で説明されているような機能的な SoE のようなアルゴリズムを作成することをお勧めします。 .looprecur

于 2013-06-15T05:43:10.710 に答える