Skip to content

Instantly share code, notes, and snippets.

@tnoda
Last active August 29, 2015 14:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tnoda/9f23492eae5b387891cc to your computer and use it in GitHub Desktop.
Save tnoda/9f23492eae5b387891cc to your computer and use it in GitHub Desktop.
Project Euler Problem 10 は Clojure でやっても 100ms 未満で計算できるはず。
(ns tnoda.pe10)
(defn- sieve
"Returns an array of primes below len. Retrieved from
https://github.com/tnoda/tnoda.math.prime."
[^long len]
(let [n len
not-prime (doto (boolean-array n)
(aset 0 true)
(aset 1 true))
primes (long-array n)]
(loop [p 0, i 2]
(if (< i n)
(if (aget not-prime i)
(recur p (inc i))
(do
(aset primes p i)
(loop [j (* i i)]
(when (< j n)
(aset not-prime j true)
(recur (+ j i))))
(recur (inc p) (inc i))))
(let [ps (long-array p)]
(System/arraycopy primes 0 ps 0 p)
ps)))))
(defn solve
[]
(let [ps (longs (sieve 2000000))]
(areduce ps i ret 0 (+ ret (aget ps i)))))
;; tnoda.pe10> (time (do (solve) nil))
;; "Elapsed time: 41.039 msecs"
;; nil
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment