Any suggestions on improvement are welcome.

(ns cina.prime-circular)

(declare least-prime-divisor-from-primes 

(defn least-prime-divisor-from-primes
  "Find the least prime divisor of an integer n. Instead of checking every integer less than n,
  use the pool of known primes instead."
  [primes n]
  (loop [[p & ps] primes
         n n]
      (= 0 (mod n p)) p
      (> (Math/pow p 2) n) n
      :else (recur ps n))))

(defn least-prime-divisor
  (least-prime-divisor-from-primes primes n))

(defn prime
  "If n's least prime divisor is itself, then it must be a prime."
    (< n 1) (throw (Exception. "Positive integer required."))
    (= n 1) false
    :else (= n (least-prime-divisor n))))

;; A lazy sequence of primes
#_(time (last (take-while #(< % 100000) primes)))
(def primes (lazy-seq
              (cons 2 (filter prime (iterate inc 3)))))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.