4clojure #67 Prime Numbers

4clojure #67 Prime Numbers

最初のx個の素数を返す関数を作る。

(= (__ 2) [2 3])
(= (__ 5) [2 3 5 7 11])
(= (last (__ 100)) 541)

はじめは、reduceのClojureDocをみて、素数列をつくろうとしましたが、 うまくいかなかったので、prime?を作ってみました。

1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことが素数 なので、その条件をコード化しました。takeで(dec n)としているのは２から 始まるiterateのためです。

あと、prime?にわたすiterateのせいで、Execution Timed Out! がでてしまうので、求める数の二乗の個数までに制限を入れました。

((fn my-prime [num]
    (letfn [(prime? [n]
               (if (>= 1 (count (filter #(= 0 (mod n %)) 
                     (take (dec n) (iterate inc 2)))))
                 true
                 false))]
    (take num (filter prime? (take (* num num) (iterate inc 2))))))
5)

prime?ができたのであらためてreduce方式のとき方を見直したらすんなりできました。

((fn my-prime [num]
  (take num
    (reduce 
        (fn inner-prime [p n]
          (if (= 0 (count (filter #(= 0 (mod n %)) p)))
            (conj p n)
            p))
      [2]
      (take (* num num) (iterate inc 3)))))
 5)

参考 reduceのClojureDocより

(reduce
  (fn [primes number]
    (if (some zero? (map (partial mod number) primes))
      primes
      (conj primes number)))
  [2]
  (take 1000 (iterate inc 3)))