fork download
  1.  
  2. (def primes
  3. " The following routine produces a infinite sequence of primes
  4. (i.e. can be infinite since the evaluation is lazy in that it
  5. only produces values as needed). The method is from clojure primes.clj library
  6. which produces primes based upon O'Neill's paper:
  7. 'The Genuine Sieve of Eratosthenes'.
  8.  
  9. Produces primes based upon trial division on previously found primes up to
  10. (sqrt number), and uses 'wheel' to avoid
  11. testing numbers which are divisors of 2, 3, 5, or 7.
  12. A full explanation of the method is available at:
  13. [https://g...content-available-to-author-only...b.com/stuarthalloway/programming-clojure/pull/12] "
  14.  
  15. (concat
  16. [2 3 5 7]
  17. (lazy-seq
  18. (let [primes-from ; generates primes by only checking if primes
  19. ; numbers which are not divisible by 2, 3, 5, or 7
  20. (fn primes-from [n [f & r]]
  21. (if (some #(zero? (rem n %))
  22. (take-while #(<= (* % %) n) primes))
  23. (recur (+ n f) r)
  24. (lazy-seq (cons n (primes-from (+ n f) r)))))
  25.  
  26. ; wheel provides offsets from previous number to insure we are not landing on a divisor of 2, 3, 5, 7
  27. wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2
  28. 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6
  29. 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]
  30. (primes-from 11 wheel)))))
  31.  
  32. (defn between [lo hi]
  33. "Primes between lo and hi value "
  34. (->> (take-while #(<= % hi) primes)
  35. (filter #(>= % lo))
  36. ))
  37.  
  38. (println "1,000,000th prime:" (nth primes (dec 1000000))) ; decrement by one since nth starts counting from 0; your code goes here
Time limit exceeded #stdin #stdout 5s 4386816KB
stdin
Standard input is empty
stdout
Standard output is empty