Project Euler Problem 3 #mitori_clj

problem_3.clj

;;; Project Euler Problem 3
;;; http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203

(use 'clojure.test)

(defn prime?
  [n]
  (if (= 1 n)
    false
    (every? (complement #(zero? (rem n %)))
            (take-while #(<= (* % %) n)
                        (cons 2 (range 3 n 2))))))

(defn prime-factor?
  [n m]
  (and (zero? (rem n m))
       (prime? m)))

;;; - 素因数が √n よりも大きい場合には正しく動かない
;;; - 素因数の指数が 2以上の場合は、シーケンスには 1つの素因数だけが含まれる
;;;   (prime-factors 12) の結果は [2 3] であり [2 2 3] ではない
(defn prime-factors
  [n]
  (cond
    (= 1 n) [1]
    (prime? n) [n]
    :else (filter (partial prime-factor? n)
                  (cons 2 (range 3 (inc (long (Math/sqrt n))) 2)))))

(is (= (last (prime-factors 13195)) 29))

(last (prime-factors 600851475143))

problem_3_2.clj

;;; Project Euler Problem 3
;;; http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203

(use 'clojure.test)

(defn prime?
  [n]
  (if (= 1 n)
    false
    (every? (complement #(zero? (rem n %)))
            (take-while #(<= (* % %) n)
                        (cons 2 (range 3 n 2))))))

(defn prime-factors
  [n]
  (if (= 1 n)
    [1]
    (let [primes (filter prime?
                         (range 2 (inc (long (Math/sqrt n)))))]
      (loop [factors [] n n]
        (if (prime? n)
          (conj factors n)
          (let [factor (first
                         (filter #(zero? (rem n %))
                                 (take-while #(<= % (long (Math/sqrt n))) primes)))]
            (recur (conj factors factor) (quot n factor))))))))

(is (= (last (prime-factors 13195)) 29))

(last (prime-factors 600851475143))

complement 覚えておきます。

ほしい場面はままあるのに、代わりになる関数があったり ( filter と remove など ) 、微妙な関数ですね。

名前が長いせいで、@tnoda のような意見が出るのかも ( https://gist.github.com/4239310/#comment-619633 ) 。

かといって代替案はありません。comp も使えませんしね ([:-P