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))

素数判定の処理を @kohyama さんの別解を参考に修正しました。

素数列を使わない解答を作ってみました． Clojure 速いです:

(loop [x 600851475143 d 2]
  (if (< x (* d d))
    x
    (if (zero? (rem x d))
      (recur (quot x d) d)
      (recur x (inc d)))))

2 から小さい順に元の数を割っていって割り切れなくなったら答えになります．どう見ても力技ですが，最悪 O(√n) な primitive loop なのと，Clojure が速いのとで，素数列を作るよりも速く，< 1ms で答えを出します．

おお. すばらしい.

Clojure 速い，すばらしい（宣伝）

先の自分の別解例ちょっと嘘がはいってました.
1 は every? で一般化できてないから, 自分の prime? だと (prime? 1) が true になっちゃいます.
問題の答えには影響ないですが, prime? の名に偽りありです. 失礼しました.
あ, max-factor も名前がおかしいな... 「素」が抜けてる.

@emanon001 さんはちゃんと 1 の場合分け残してる.

complement 覚えておきます。

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

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

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