Prime numbers in Clojure

primes.clj

(def prime-numbers
  ((fn f [x]
     (cons x
       (lazy-seq
         (f (first
              (drop-while
                (fn [n]
                  (some #(zero? (mod n %))
                    (take-while #(<= (* % %) n) prime-numbers)))
                (iterate inc (inc x))))))))
   2))

Explanation

in English

prime-numbers is the sequence gotten by applying 2 to the function f.

The function f, when a prime x is given, returns a sequence that is consed x to the lazy-seqed sequence which is returned by f with the prime number next to x.

The prime number next to x is the first element of the sequence that elements are dropped while it is a composed number from the iteratedly increasing sequence by 1 from the number increased by 1 from x.

A number n is composed one when it is divided by some elements that are taken while it's less than or equal to the positive square root of n from the prime-numbers.

Though we use prime-numbers to ask prime-numbers, things go well because the primes whose square is less than or equal to the candidates of the prime next to it are already gotten.
The first prime '2' is all what we should supply.

日本語

素数列 prime-numbers は, 関数 f の引数に 2 を与えて得られる数列です.

関数 f は, 素数 x を与えると, 次の素数 (first ...) を関数 f に与えて得られる数列を遅延シーケンスにしたもの (lazy-seq ...) の先頭に x を付加したシーケンス (cons x ...) を返します.

ある素数 x の次の素数は, x の次の数 (inc x) から 1ずつ増加する数列 (iterate inc ...) から, 要素が合成数である間, 要素を捨てたシーケンス (drop-while ...) の最初の要素です.

数 n が合成数であるかどうか (fn [n] ...) は, 素数列 prime-numbers のうち, n の正の平方根以下である間要素を取り出したシーケンス (take-while #(<= (* % %) n) prime-numbers) の中に, n を割り切る #(zero? (mod n %)) ものが一つ以上あるか (some ...) で判定します.

素数列 prime-numbers を求めるのに, 素数列 prime-numbers を使っていますが, 次の素数の候補に対して, 二乗がその数以下であるような素数までは求まっているので, 最初の素数 2 だけ用意すれば大丈夫.

Example to use

100 primes from 2

user=> (take 100 prime-numbers)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541)

primes less than 100

user=> (take-while #(< % 100) prime-numbers)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

primes greater than or equal to 9,000 and less than 10,000

user=> (take-while #(< % 10000) (drop-while #(< % 9000) prime-numbers))
(9001 9007 9011 9013 9029 9041 9043 9049 9059 9067 9091 9103 9109 9127 9133 9137 9151 9157 9161 9173 9181 9187 9199 9203 9209 9221 9227 9239 9241 9257 9277 9281 9283 9293 9311 9319 9323 9337 9341 9343 9349 9371 9377 9391 9397 9403 9413 9419 9421 9431 9433 9437 9439 9461 9463 9467 9473 9479 9491 9497 9511 9521 9533 9539 9547 9551 9587 9601 9613 9619 9623 9629 9631 9643 9649 9661 9677 9679 9689 9697 9719 9721 9733 9739 9743 9749 9767 9769 9781 9787 9791 9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929 9931 9941 9949 9967 9973)

total sum of primes below 10

user=> (apply + (take-while #(< % 10) prime-numbers))
17

total sum of primes below 2,000,000

user=> (time (apply + (take-while #(< % 2000000) prime-numbers)))
"Elapsed time: 6372.194 msecs"

The answer itself is hidden because it is the answer of https://projecteuler.net/problem=10

Thank you.
It's really helping me