2
\$\begingroup\$

Any suggestions on improvement are welcome.

(ns cina.prime-circular)

(declare least-prime-divisor-from-primes 
         least-prime-divisor
         prime
         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]
    (cond
      (= 0 (mod n p)) p
      (> (Math/pow p 2) n) n
      :else (recur ps n))))

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

(defn prime
  "If n's least prime divisor is itself, then it must be a prime."
  [n]
  (cond
    (< 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)))))
\$\endgroup\$

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.