Re: Can anyone create a simpler version of prime factors in Clojure?
Here's my awful terrible code which is a direct translation from a
java version I wrote and needs a fast functional sieve: I prefer
Cristophe Grande's.
http://clj-me.cgrand.net/index.php?s=Everybody%20loves%20the%20Sieve%20of%20Eratosthenes
The one in contrib is pretty good as well.
(letfn [(n-p [n prime pow]
(if (zero? (rem n prime))
(recur (/ n prime) prime (inc pow))
[n pow]))
(get-primes [lim n primes]
(let [p (first primes)]
(cond
(= n 1) (list)
(or (empty? primes) ( (* p p) lim)) [[n 1]]
:else (let [np (n-p n p 0)]
(if (zero? (second np))
(recur lim n (rest primes))
(lazy-cat [[p (second np)]]
(get-primes lim (first np)
(rest
primes]
(defn prime-factors
([n primes]
(if ( n 2)
(list)
(lazy-seq (get-primes n n primes
([n] (prime-factors n (take-while #(= (* % %) n) (primes))
On Jun 11, 2:15 pm, russellc russell.christop...@gmail.com wrote:
Not sure it's better than Uncle Bobs version but it seems a little
more idiomatic?
(defn of [n]
(letfn [(f [res k]
(if (= 0 (rem (:n res) k))
(assoc (assoc res :n (quot (:n res) k)) :fs (conj (:fs
res) k))
res))]
(:fs (reduce f {:n n :fs []} (range 2 n)
Uncle Bob version below (http://blog.objectmentor.com/articles/
2010/05/15/clojure-prime-factors)
(defn of
([n]
(of [] n 2))
([factors n candidate]
(cond
(= n 1) factors
(= 0 (rem n candidate)) (recur (conj factors candidate) (quot n
candidate) candidate)
( candidate (Math/sqrt n)) (conj factors n)
:else (recur factors n (inc candidate))
)
)
)
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Re: Can anyone create a simpler version of prime factors in Clojure?
I looked through some of my Project Euler solutions and found this version. It is essentially the same as Uncle Bob's, but to my eye it is a bit easier to read. (defn least-nontrivial-divisor [n];; integer n 1 (loop [k 2] (cond (zero? (rem n k)) k ;; k divides n, return k ( (* k k) n ) n ;; k sqrt n, return n :else (recur (inc k) (defn prime-factors [n];; integer n 1 (loop [n n factors []] (if (= 1 n) factors (let [d (least-nontrivial-divisor n)] (recur (quot n d) (conj factors d)) -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Can anyone create a simpler version of prime factors in Clojure?
On 11 Jun 2010, at 20:35, Russell Christopher wrote:
didn't need the assoc in my previous try
(defn of [n]
(letfn [(f [res k]
(if (= 0 (rem (:n res) k))
{:n (/ (:n res) k) :fs (conj (:fs res) k)}
res))]
(:fs (reduce f {:n n :fs []} (range 2 n)
The two give different answers. Given n=144, your version produces [2 3 4 6]
and Uncle Bob's produces [2 2 2 2 3 3].
-Steve
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Re: Can anyone create a simpler version of prime factors in Clojure?
On 12 Jun 2010, at 16:18, Russell Christopher wrote: You're right. Hope I haven't offended with the fail, I thought I had tested it - by iterating over a range and comparing it to Uncle Bob's but obviously I didn't do that right and then realized that factorization is likely not O(n) anyway. I'll probably take more time next time. No offense was caused. I thought I'd tinker with the code, aiming to replace the :n :fs with destructuring, and then got distracted by the pedantic matter of correctness. :-) -Steve -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Can anyone create a simpler version of prime factors in Clojure?
I focused more on idiom than correctness (obviously). Took a risk with not much effort except to see if I could do any better with a toy problem. The answer was no, Uncle Bob's is idiomatic modulo some minor things. On Sat, Jun 12, 2010 at 12:59 PM, Steve Purcell st...@sanityinc.com wrote: On 12 Jun 2010, at 16:18, Russell Christopher wrote: You're right. Hope I haven't offended with the fail, I thought I had tested it - by iterating over a range and comparing it to Uncle Bob's but obviously I didn't do that right and then realized that factorization is likely not O(n) anyway. I'll probably take more time next time. No offense was caused. I thought I'd tinker with the code, aiming to replace the :n :fs with destructuring, and then got distracted by the pedantic matter of correctness. :-) -Steve -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Can anyone create a simpler version of prime factors in Clojure?
Not sure it's better than Uncle Bobs version but it seems a little
more idiomatic?
(defn of [n]
(letfn [(f [res k]
(if (= 0 (rem (:n res) k))
(assoc (assoc res :n (quot (:n res) k)) :fs (conj (:fs
res) k))
res))]
(:fs (reduce f {:n n :fs []} (range 2 n)
Uncle Bob version below (http://blog.objectmentor.com/articles/
2010/05/15/clojure-prime-factors)
(defn of
([n]
(of [] n 2))
([factors n candidate]
(cond
(= n 1) factors
(= 0 (rem n candidate)) (recur (conj factors candidate) (quot n
candidate) candidate)
( candidate (Math/sqrt n)) (conj factors n)
:else (recur factors n (inc candidate))
)
)
)
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Re: Can anyone create a simpler version of prime factors in Clojure?
didn't need the assoc in my previous try
(defn of [n]
(letfn [(f [res k]
(if (= 0 (rem (:n res) k))
{:n (/ (:n res) k) :fs (conj (:fs res) k)}
res))]
(:fs (reduce f {:n n :fs []} (range 2 n)
On Fri, Jun 11, 2010 at 3:15 PM, russellc russell.christop...@gmail.comwrote:
Not sure it's better than Uncle Bobs version but it seems a little
more idiomatic?
(defn of [n]
(letfn [(f [res k]
(if (= 0 (rem (:n res) k))
(assoc (assoc res :n (quot (:n res) k)) :fs (conj (:fs
res) k))
res))]
(:fs (reduce f {:n n :fs []} (range 2 n)
Uncle Bob version below (http://blog.objectmentor.com/articles/
2010/05/15/clojure-prime-factors)
(defn of
([n]
(of [] n 2))
([factors n candidate]
(cond
(= n 1) factors
(= 0 (rem n candidate)) (recur (conj factors candidate) (quot n
candidate) candidate)
( candidate (Math/sqrt n)) (conj factors n)
:else (recur factors n (inc candidate))
)
)
)
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
