-
-
Save tnoda/4342901 to your computer and use it in GitHub Desktop.
| (ns tnoda.projecteuler.problem-12 | |
| (:use [org.clojars.tnoda.math.prime :only [sieve* prime-factors *prime-array*]] | |
| clojure.test)) | |
| (defn- solver* | |
| "Returns the value of the first triangle number to have over x divisors." | |
| [x] | |
| (binding [*prime-array* (sieve*)] | |
| (let [triangle-numbers (reductions + (range)) | |
| nd (fn number-of-divisors | |
| [x] | |
| (->> (prime-factors x) | |
| vals | |
| (map inc) | |
| (apply *)))] | |
| (->> triangle-numbers | |
| (drop-while #(>= x (nd %))) | |
| first)))) | |
| (def solver (partial solver* 500)) | |
| (is (= 28 (solver* 5))) |
直感的には、素数列というのは、πなど と同様の定数としてだれかが提供してくれるべきものだと思いますので、Math/Primes みたいに使えるのがいいと思います。 [...]
同じ意見です．理想的には言語組込みの素数列シーケンスがあってもいいかもしれないのですが，それをどのようにして提供するのかというのが，使われかたにもよるので，一つに決めきれないのが難しいところです．
ということで、 僕は、素数列をストーリームとしてしまって、 with-openが使えるようにするの がいいと思います。
with-primes というマクロを作って，その中では，最初の一回だけ sieve して，その素数列を使い回すようにするというのを考えているのですが，どうでしょうか．（with-primes マクロの実体は (binding [*prime-array* (sieve*)] ...) なんですけどね．）
私も解いてみて、約数の個数を求めるのを (count (filter #(zero? (mod n %)) (range 1 (inc n)))) のnaive実装でいつまでたっても実行が終わらずに、@kohyama さんの指摘どおりしばらくハマっていました。
少しかんがえて素因数分解に落ち着いて、最終的には @tnoda さんのコードとほぼ同じになりました。
tnoda/math/prime.clj 書き方や語彙が参考になります。
別の問題で作っていた素因数分解結果をシーケンスにする関数を、この問題向けにmapにするように書きなおしていたのですが、実はfrequenciesでいいのですね。覚えます。
reductions、こういう関数ないかなあと少し探してはみたのですが、見つけられませんでした。
語彙がもっとほしいです。もしくはもっと上手く探せるようになりたいです。でも、こうやってちょっとずつ覚えていくの楽しいですね。
Project Euler始めてからWikipediaのお世話になることが多くなって、おかげで整数論？関係の知識が増えました。で、感謝の印に、毎年Wikipediaに寄付(ちょっとですが)するようになりました。
拝見しました。 いいですね。
dynamic変数にしてあるのは、なぜとは言えませんが、変な感じがします。
直感的には、素数列というのは、πなど と同様の定数としてだれかが提供してくれるべきものだと思いますので、Math/Primes みたいに使えるのがいいと思います。 ですが、実際のことを考えると、動的に生成すにしても、いらなくなったらメモリの無駄なので、消えてほしいわけです。
ということで、 僕は、素数列をストーリームとしてしまって、 with-openが使えるようにするの がいいと思います。
でも、with-openするたびに素数列を作ることになるので、非効率だよとかいう場面も多いと思いますので、素数の使われかたによるという結論ではないでしょうか。
実運用だったら、DBに突っこんでおくという、元も子もない解決策になりそうですね。
駄文失礼。