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

まずは素因数の列を作成しよう、ということで、整数 n が与えられた場合に、
2 から √n までの整数の列について、n の素因数であるかどうかでフィルタリングをかけています。(n が 1 などの特殊ケースを除いて)
あとは、作成した素因数の列について末尾の数を取得して、という感じです。

１点だけ。
(range 2 (inc (long (Math/sqrt n))))
でシーケンスを作ってますが、2より大きい整数のうち偶数は端から素数ではないので、シーケンスに含めないほうが得かと。
range 関数には (range start end step) というように step 指定ができるので、
(range 3 (inc (long (Math/sqrt n))) 2)
と指定してもよいかと思います(間違ってたらごめんなさい。test では OK でした)。
(time (last (prime-factors 600851475143))) で elapsed を測るとそれなりに差がでるかと。自分の環境では、
before
; => "Elapsed time: 276.914 msecs"
after
; => "Elapsed time: 125.847 msecs"
という感じです。

問題中の例題でテストを書いているのが良いと思いました.
自分のときもそうしよう.

1秒以下で答えが出てるので, 効率化しなくても良いとは思いますが,
ponkore さんの range の step 引数で, 偶数を除く案は費用対効果が高いのでありだと思います.

素数列があれば, 試し割りに使う数列は素数列を使うところですが,
別途求めてあるのでない限り費用対効果が低いので, ここでは要らないですね.
私の担当, 問題 10では素数列そのものが要るので, そっちで頑張ります.

問題中の例題でテストを書いているのが良いと思いました.
自分のときもそうしよう.

これ，私もいいなと思いましたので 次から 自分のときもそうしようと思います．

(inc :ponkore)

指摘内容を元に修正しました。

また、別解として『素因数が 2 のみ、または √n よりも大きい素因数が含まれている』場合でも動くものをあげました。

(complement #(zero? (rem n %))) は私だったら #(pos? (rem n %)) と書きそうです．

返答

@kohyama
費用対効果が高くて幸せになりました。
問題 10 の素数列、期待しております。

@tnoda
そちらの方がシンプルでコードの意図が読み取りやすい気がします。
『n を m で割り切れないか』という述語として、(complement #(zero? (rem n %))) の記述はやりすぎで読み取りにくいかもしれません。

修正

• 最初の解答の関数 prime-factors にコメントを追加しました。
• 最初の解答の関数 prime-factors について、整数 n の素因数に 2が含まれている場合でも正しい値が返るように修正しました。

修正して、元に戻してを繰り返すことで無駄順調にリビジョンを重ねております……

自分でもやってみました.
別途 gist 立てた方が良かったでしょうか. とりあえずここに貼ります.
別解ということで, 参考まで.

(use 'clojure.test)

(defn prime? [n]
  (->> (cons 2 (range 3 n 2))
    (take-while #(< (* % %) n))
    (every? #(pos? (rem n %)))))

(defn max-factor [n]
  (loop [d 2 n n]
    (cond (prime? n) n
          (zero? (rem n d)) (recur d (quot n d))
          :else (recur (if (= d 2) (inc d) (+ d 2)) n))))

(is (= (max-factor 13195) 29))

(time (max-factor 600851475143))

ポイント

• 試し割りの列に 2 も入れてあげれば every? だけで一般化できます.
• 試し割りの列を正の平方根以下に限定するのに Math/sqrt を使わず #(< (* % %) n) で take-while してみました.
• 素因数分解の結果自体は求められていないので, 一般性は下がりますが,
  (2 3 5 7 9 ... ) で割り切れる間は順に割っていき, 素数になった時点でそれが最大の素因数
  ということで答えを返しています.

partialにcomplementにと、おいしそうなコンビネータがでてきて楽しいです。勉強になります。
clojureはdocですぐ説明見れるのがいいですね。(とかいうとCommon Lispのひとに怒られそうですが)

私の解も晒しておきます。
√n 以下の素数を全部求めたあとで、nをひたすら割り続ける解です。途中でバグに気づいて直したところ、結局素因数分解になりました。
素数求めてる意味があんまりないような気がしたりなどおそらくツッコミどころだらけですが……w
https://gist.github.com/4250659

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