euler003.clj

; Problem 3
; The prime factors of 13195 are 5, 7, 13 and 29.
; What is the largest prime factor of the number 600851475143 ?

(defn prime? [x]
  (cond (< x 2) false
	(= x 2) true
	(even? x) false
	:else (let [boundary (inc (int (Math/sqrt x)))
		    candidates (range 3 boundary 2)]
		(empty? (drop-while #(pos? (mod x %)) candidates)))))


(def memoized_prime? (memoize prime?))

(def primes
     (cons 2 (filter memoized_prime? (iterate #(+ 2 %) 1))))

(def limit 600851475143)
(def limit* 13195)

(defn prime-factors [x]
  (let [boundary (inc (int (Math/sqrt x)))]
    (take-while #(< % boundary) 
		(filter #(zero? (mod x %)) primes))))


(prime-factors limit*)       ; => (5 7 13 29)
(last (prime-factors limit)) ; => 6857