problem-3.clj

(ns project-euler.problem-3)

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

(def n 600851475143)

(defn factors [n]
  (let [half (long (/ n 2))]
    (filter #(= (rem half %) 0) (range 1 (inc half)))))

(defn prime?
  "The AKS algorithm for testing primality of n"
  [^long n]
  (cond
   (= n 2) true
   (= n 3) true
   (= (mod n 2) 0) false
   (= (mod n 3) 0) false
   :else (loop [i 5, w 2]
           (if (<= (* i i) n)
             (if (= (mod n i) 0)
               false
               (recur (+ i w) (- 6 w)))
             true))))

(defn largest-prime-factor [^long n]
  (loop [prev (quot n 2)]
    (if (zero? (rem n prev))
      (if (prime? prev) prev (recur (dec prev)))
      (recur (dec prev)))))