Sekvencia prvočísel v rozsahu - matematika, clojure

Chcel by som napísať funkciu prime-seq na zobrazenie zoznamu medzi dvoma číslami pomocou from a to.

Tu je môj kód, myslím si, že ak sú čísla zo zoznamu pravdivé, zobrazte ich. Ale neviem, ako to napísať, som pre tento jazyk veľmi nový.

(defn is-prime? [n]
(empty?
(filter #(= 0 (mod n %)) (range 2 n))))

(defn prime-seq [from to]
(drop from (take to is-prime?)))

výsledkom by malo byť:

(prime-seq 1 5)
=> (2 3 5)

odpovede:

0 pre odpoveď č. 1

Ste veľmi blízko:

(defn is-prime? [n]
(empty? (filter #(= 0 (mod n %)) (range 2 n))))

(defn prime-seq [from to]
(filter is-prime? (range from (inc to))))

(prime-seq 1 29)
=> (1 2 3 5 7 11 13 17 19 23 29)

Používa sa to range vygenerovať sekvenciu všetkých čísel medzi from a to (vrátane) filterpomocou tohto zoznamu is-prime? predikát.

Čo sa týka vášho is-prime? predikát, existuje veľa prístupov k určovaniu prvoradosti. Ako komentujete (mod 1 1) => 0, takže váš predikát sa vráti ako pravdivý, ale 1 nie je prvočíslo. Do predikátu môžete jednoducho pridať špeciálny prípad tak, že sa vráti akékoľvek číslo menšie ako 2. false:

(defn is-prime? [n]
(if (< 1 n)
(empty? (filter #(= 0 (mod n %)) (range 2 n)))
false))

Alebo trochu jemnejšie použitie and:

(defn is-prime? [n]
(and (< 1 n)
(not (some #(= 0 (mod n %)) (range 2 n)))))

---

0 pre odpoveď č. 2

V prípade, že sem ľudia prichádzajú za primerane rýchlym algoritmom na nájdenie prvočísel implementovaných v Clojure, tu je implementácia Sieve z Eratosthenes v Clojure (pomocou polí JVM):

(defn find-primes
"Finds all prime numbers less than n, returns them sorted in a vector"
[n]
(if (< n 2)
[]
(let [^booleans sieve (boolean-array n false)
s (-> n Math/sqrt Math/floor int)]
(loop [p 2]
(if (> p s)
(into []
(remove #(aget sieve %))
(range 2 n))
(do
(when-not (aget sieve p)
(loop [i (* 2 p)]
(when (< i n)
(aset sieve i true)
(recur (+ i p)))))
(recur (inc p))))))))

Príklad:

(find-primes 100)
=> [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]

A niektoré benchmarking:

(require "[criterium.core :as bench])

(bench/bench
(find-primes 100000))

;Evaluation count : 17940 in 60 samples of 299 calls.
;             Execution time mean : 3.370834 ms
;    Execution time std-deviation : 217.730604 µs
;   Execution time lower quantile : 3.040426 ms ( 2.5%)
;   Execution time upper quantile : 3.792958 ms (97.5%)
;                   Overhead used : 1.755126 ns

---