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

Project Eulerを解いていると素数列が必要な問題が沢山出てきます。 また、素数の判定はかなりコストのかかる作業なので、1つずつ判定していると、時間が足りないことが多くなってきます。

そんなときにRich Hickeyさんの作ったエラトステネスの篩https://gist.github.com/1533726を見つけて、これで100万くらいまであらかじめ作っておいて使ってます。 それでも3秒くらいなので、有用かと。

@kohyama

• そうか、試し割りの列に 2 を含めれば、効率的にも場合分けは全く必要ないですね。
• 試し割りの列を絞り込む方法はそちらの方が好きです。(シーケンスを作って、加工してという作業自体が楽しいというか……)

@plaster

• partial を使うと、「あ、何か関数型っぽい」という感覚が未だつきまとっています(笑)
• doc さんは素晴しい方です。 doc-string さんは少し影が薄いですが良い方です。
• 別解あとで読みます!

@ypsilon-takai
おお、有用な情報ありがとうございます。
噂には聞いていましたが、Project Euler は素数列を必要とする問題がたくさん出てくるのですね。……ゴクリ。

素数判定の処理を @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