Skip to content

Instantly share code, notes, and snippets.

@rpdillon
Created April 11, 2011 14:49
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 rpdillon/913636 to your computer and use it in GitHub Desktop.
Save rpdillon/913636 to your computer and use it in GitHub Desktop.
Project Euler #3 in Clojure
(defn primes-until
"A tail-recursive primes generator that generates primes until
<stop-pred> returns true. <stop-pred> is a function that
takes in the current candidate prime and the number of primes
generated so far and returns true or false."
[stop-pred]
(defn rec
"p: vector of primes found so far; i: candidate prime"
[p i] (cond
(stop-pred i (count p)) p
(let [root (. Math (sqrt i))]
(every? #(not= (rem i %) 0) (take-while #(<= % root) p))) (recur (conj p i) (inc i))
true (recur p (inc i))))
(rec [] 2))
(defn prime-factor
"Find the prime factors of <i> using a collection of primes <p>.
<f> is a list of prime factors found so far."
[i p f]
(cond (= i 1) f
(= 0 (rem i (first p))) (recur (/ i (first p)) p (cons (first p) f))
true (recur i (rest p) f)))
(prime-factor 600851475143 (primes-until (fn [i n] (> i 10000))) nil)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment