Skip to content

Instantly share code, notes, and snippets.

@blinsay

blinsay/euler5.clj

Last active December 22, 2015 19:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save blinsay/6520793 to your computer and use it in GitHub Desktop.
Save blinsay/6520793 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
euler5.clj
(defmacro divides?
"Return true if y divides x. Expands to (= 0 (mod x y))"
[x y]
`(zero? (mod ~x ~y)))
(defn prime?
"Check to see if a number is prime. Naive"
[n]
(let [r (inc (Math/floor (Math/sqrt n)))]
(nil? (some #(divides? n %) (range 2 r)))))
(defn prime-divisors
"A lazy-seq of all of the prime divisors of n between 2 and sqrt(n)"
[n]
(let [r (inc (Math/floor (Math/sqrt n)))]
(filter prime? (filter #(divides? n %) (range 2 r)))))
(defn prime-factors
"Generate the prime factorization of n as a seq"
[n]
((fn [x accum]
(if (prime? x)
(cons x accum)
(let [d (first (prime-divisors x))]
(recur (/ x d) (cons d accum)))))
n []))
(defn counts
"Given a collection, returns a map from items in the collection to the number
of times they occur"
[xs]
(reduce #(assoc %1 %2 (inc (get %1 %2 0))) {} xs))
(defn get-answer []
(let [factor-counts (map #(counts (prime-factors %)) (range 1 (inc n)))]
(reduce-kv #(apply * %1 (repeat %3 %2)) 1 (apply merge-with max factor-counts)))))
@skatenerd
Copy link

merge-with is pretty cool. good to know that exists.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment