Wednesday, November 16, 2011

Project Euler in Clojure

Problem 3; what's the biggest prime factor of some big #?

I went a lot of ways here, but finally ended up with the following. First, I made a function which would factor a number. I poked at this a lot of times before I ended up on the for comprehension, which I'm not sure is the best way by far, but I wanted to play with it. It runs up a counter from 2 to the sqrt(target), and if the target MOD the number is 0, returns the number and the "other" factor in a list, then flattens the list of lists when done. (Ideas welcome for removing the flatten... something with cons/conj?)

Then I wrote a "prime" method which tells me if a number is prime. It does this by just factoring the number using my factor func, then counts the factors. If it's 2, it's prime (1 and the # itself).

Then it was a simple matter of calling factor on my big #, filtering the factors returned through the prime method, and calling max on the result. Ah, but max doesn't take a seq... so I had to 'apply' max to the result. Lots of lessons learned here, and looking for advice on how this could be more clojurific.

(defn factor [m] (flatten (for [a (range 1 (Math/sqrt m)) :when (zero? (mod m a))] (list a (/ m a)))))

(defn prime [n] (= 2 (count (factor n))))

(apply max (filter prime (factor 600851475143)))

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home