How to resolve the algorithm Sieve of Eratosthenes step by step in the Clojure programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sieve of Eratosthenes step by step in the Clojure programming language
Table of Contents
Problem Statement
The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer.
Implement the Sieve of Eratosthenes algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn't optimize by using pre-computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes. If there's an easy way to add such a wheel based optimization, implement it as an alternative version.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sieve of Eratosthenes step by step in the Clojure programming language
Source code in the clojure programming language
(defn primes< [n]
(remove (set (mapcat #(range (* % %) n %)
(range 2 (Math/sqrt n))))
(range 2 n)))
(defn primes< [n]
(remove (into #{}
(mapcat #(range (* % %) n %)
(range 2 (Math/sqrt n))))
(range 2 n)))
(defn primes< [n]
(if (< n 2) ()
(cons 2 (remove (into #{}
(mapcat #(range (* % %) n %)
(range 3 (Math/sqrt n) 2)))
(range 3 n 2)))))
(defn primes-to
"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"
[n]
(let [root (-> n Math/sqrt long),
cmpsts (boolean-array (inc n)),
cullp (fn [p]
(loop [i (* p p)]
(if (<= i n)
(do (aset cmpsts i true)
(recur (+ i p))))))]
(do (dorun (map #(cullp %) (filter #(not (aget cmpsts %))
(range 2 (inc root)))))
(filter #(not (aget cmpsts %)) (range 2 (inc n))))))
(defn primes-to
"Returns a lazy sequence of prime numbers less than lim"
[lim]
(let [refs (boolean-array (+ lim 1) true)
root (int (Math/sqrt lim))]
(do (doseq [i (range 2 lim)
:while (<= i root)
:when (aget refs i)]
(doseq [j (range (* i i) lim i)]
(aset refs j false)))
(filter #(aget refs %) (range 2 lim)))))
(defn primes-to
"Returns a lazy sequence of prime numbers less than lim"
[lim]
(let [max-i (int (/ (- lim 1) 2))
refs (boolean-array max-i true)
root (/ (dec (int (Math/sqrt lim))) 2)]
(do (doseq [i (range 1 (inc root))
:when (aget refs i)]
(doseq [j (range (* (+ i i) (inc i)) max-i (+ i i 1))]
(aset refs j false)))
(cons 2 (map #(+ % % 1) (filter #(aget refs %) (range 1 max-i)))))))
(defn primes-to
"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"
[n]
(letfn [(nxtprm [cs] ; current candidates
(let [p (first cs)]
(if (> p (Math/sqrt n)) cs
(cons p (lazy-seq (nxtprm (-> (range (* p p) (inc n) p)
set (remove cs) rest)))))))]
(nxtprm (range 2 (inc n)))))
(defn primes-to
"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"
[max-prime]
(let [sieve (fn [s n]
(if (<= (* n n) max-prime)
(recur (if (s n)
(reduce #(assoc %1 %2 false) s (range (* n n) (inc max-prime) n))
s)
(inc n))
s))]
(->> (-> (reduce conj (vector-of :boolean) (map #(= % %) (range (inc max-prime))))
(assoc 0 false)
(assoc 1 false)
(sieve 2))
(map-indexed #(vector %2 %1)) (filter first) (map second))))
(set! *unchecked-math* true)
(defn primes-to
"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"
[n]
(let [root (-> n Math/sqrt long),
rootndx (long (/ (- root 3) 2)),
ndx (long (/ (- n 3) 2)),
cmpsts (long-array (inc (/ ndx 64))),
isprm #(zero? (bit-and (aget cmpsts (bit-shift-right % 6))
(bit-shift-left 1 (bit-and % 63)))),
cullp (fn [i]
(let [p (long (+ i i 3))]
(loop [i (bit-shift-right (- (* p p) 3) 1)]
(if (<= i ndx)
(do (let [w (bit-shift-right i 6)]
(aset cmpsts w (bit-or (aget cmpsts w)
(bit-shift-left 1 (bit-and i 63)))))
(recur (+ i p))))))),
cull (fn [] (loop [i 0] (if (<= i rootndx)
(do (if (isprm i) (cullp i)) (recur (inc i))))))]
(letfn [(nxtprm [i] (if (<= i ndx)
(cons (+ i i 3) (lazy-seq (nxtprm (loop [i (inc i)]
(if (or (> i ndx) (isprm i)) i
(recur (inc i)))))))))]
(if (< n 2) nil
(cons 3 (if (< n 3) nil (do (cull) (lazy-seq (nxtprm 0)))))))))
(defn primes-tox
"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"
[n]
(let [root (-> n Math/sqrt long),
rootndx (long (/ (- root 3) 2)),
ndx (max (long (/ (- n 3) 2)) 0),
lmt (quot ndx 64),
cmpsts (long-array (inc lmt)),
cullp (fn [i]
(let [p (long (+ i i 3))]
(loop [i (bit-shift-right (- (* p p) 3) 1)]
(if (<= i ndx)
(do (let [w (bit-shift-right i 6)]
(aset cmpsts w (bit-or (aget cmpsts w)
(bit-shift-left 1 (bit-and i 63)))))
(recur (+ i p))))))),
cull (fn [] (do (aset cmpsts lmt (bit-or (aget cmpsts lmt)
(bit-shift-left -2 (bit-and ndx 63))))
(loop [i 0]
(when (<= i rootndx)
(when (zero? (bit-and (aget cmpsts (bit-shift-right i 6))
(bit-shift-left 1 (bit-and i 63))))
(cullp i))
(recur (inc i))))))
numprms (fn []
(let [w (dec (alength cmpsts))] ;; fast results count bit counter
(loop [i 0, cnt (bit-shift-left (alength cmpsts) 6)]
(if (> i w) cnt
(recur (inc i)
(- cnt (java.lang.Long/bitCount (aget cmpsts i))))))))]
(if (< n 2) nil
(cons 2 (if (< n 3) nil
(do (cull)
(deftype OPSeq [^long i ^longs cmpsa ^long cnt ^long tcnt] ;; for arrays maybe need to embed the array so that it doesn't get garbage collected???
clojure.lang.ISeq
(first [_] (if (nil? cmpsa) nil (+ i i 3)))
(next [_] (let [ncnt (inc cnt)] (if (>= ncnt tcnt) nil
(OPSeq.
(loop [j (inc i)]
(let [p? (zero? (bit-and (aget cmpsa (bit-shift-right j 6))
(bit-shift-left 1 (bit-and j 63))))]
(if p? j (recur (inc j)))))
cmpsa ncnt tcnt))))
(more [this] (let [ncnt (inc cnt)] (if (>= ncnt tcnt) (OPSeq. 0 nil tcnt tcnt)
(.next this))))
(cons [this o] (clojure.core/cons o this))
(empty [_] (if (= cnt tcnt) nil (OPSeq. 0 nil tcnt tcnt)))
(equiv [this o] (if (or (not= (type this) (type o))
(not= cnt (.cnt ^OPSeq o)) (not= tcnt (.tcnt ^OPSeq o))
(not= i (.i ^OPSeq o))) false true))
clojure.lang.Counted
(count [_] (- tcnt cnt))
clojure.lang.Seqable
(clojure.lang.Seqable/seq [this] (if (= cnt tcnt) nil this))
clojure.lang.IReduce
(reduce [_ f v] (let [c (- tcnt cnt)]
(if (<= c 0) nil
(loop [ci i, n c, rslt v]
(if (zero? (bit-and (aget cmpsa (bit-shift-right ci 6))
(bit-shift-left 1 (bit-and ci 63))))
(let [rrslt (f rslt (+ ci ci 3)),
rdcd (reduced? rrslt),
nrslt (if rdcd @rrslt rrslt)]
(if (or (<= n 1) rdcd) nrslt
(recur (inc ci) (dec n) nrslt)))
(recur (inc ci) n rslt))))))
(reduce [this f] (if (nil? i) (f) (if (= (.count this) 1) (+ i i 3)
(.reduce ^clojure.lang.IReduce (.next this) f (+ i i 3)))))
clojure.lang.Sequential
Object
(toString [this] (if (= cnt tcnt) "()"
(.toString (seq (map identity this))))))
(->OPSeq 0 cmpsts 0 (numprms))))))))
(defn primes-Bird
"Computes the unbounded sequence of primes using a Sieve of Eratosthenes algorithm by Richard Bird."
[]
(letfn [(mltpls [p] (let [p2 (* 2 p)]
(letfn [(nxtmltpl [c]
(cons c (lazy-seq (nxtmltpl (+ c p2)))))]
(nxtmltpl (* p p))))),
(allmtpls [ps] (cons (mltpls (first ps)) (lazy-seq (allmtpls (next ps))))),
(union [xs ys] (let [xv (first xs), yv (first ys)]
(if (< xv yv) (cons xv (lazy-seq (union (next xs) ys)))
(if (< yv xv) (cons yv (lazy-seq (union xs (next ys))))
(cons xv (lazy-seq (union (next xs) (next ys)))))))),
(mrgmltpls [mltplss] (cons (first (first mltplss))
(lazy-seq (union (next (first mltplss))
(mrgmltpls (next mltplss)))))),
(minusStrtAt [n cmpsts] (loop [n n, cmpsts cmpsts]
(if (< n (first cmpsts))
(cons n (lazy-seq (minusStrtAt (+ n 2) cmpsts)))
(recur (+ n 2) (next cmpsts)))))]
(do (def oddprms (cons 3 (lazy-seq (let [cmpsts (-> oddprms (allmtpls) (mrgmltpls))]
(minusStrtAt 5 cmpsts)))))
(cons 2 (lazy-seq oddprms)))))
(defn primes-treeFolding
"Computes the unbounded sequence of primes using a Sieve of Eratosthenes algorithm modified from Bird."
[]
(letfn [(mltpls [p] (let [p2 (* 2 p)]
(letfn [(nxtmltpl [c]
(cons c (lazy-seq (nxtmltpl (+ c p2)))))]
(nxtmltpl (* p p))))),
(allmtpls [ps] (cons (mltpls (first ps)) (lazy-seq (allmtpls (next ps))))),
(union [xs ys] (let [xv (first xs), yv (first ys)]
(if (< xv yv) (cons xv (lazy-seq (union (next xs) ys)))
(if (< yv xv) (cons yv (lazy-seq (union xs (next ys))))
(cons xv (lazy-seq (union (next xs) (next ys)))))))),
(pairs [mltplss] (let [tl (next mltplss)]
(cons (union (first mltplss) (first tl))
(lazy-seq (pairs (next tl)))))),
(mrgmltpls [mltplss] (cons (first (first mltplss))
(lazy-seq (union (next (first mltplss))
(mrgmltpls (pairs (next mltplss))))))),
(minusStrtAt [n cmpsts] (loop [n n, cmpsts cmpsts]
(if (< n (first cmpsts))
(cons n (lazy-seq (minusStrtAt (+ n 2) cmpsts)))
(recur (+ n 2) (next cmpsts)))))]
(do (def oddprms (cons 3 (lazy-seq (let [cmpsts (-> oddprms (allmtpls) (mrgmltpls))]
(minusStrtAt 5 cmpsts)))))
(cons 2 (lazy-seq oddprms)))))
(deftype CIS [v cont]
clojure.lang.ISeq
(first [_] v)
(next [_] (if (nil? cont) nil (cont)))
(more [this] (let [nv (.next this)] (if (nil? nv) (CIS. nil nil) nv)))
(cons [this o] (clojure.core/cons o this))
(empty [_] (if (and (nil? v) (nil? cont)) nil (CIS. nil nil)))
(equiv [this o] (loop [cis1 this, cis2 o] (if (nil? cis1) (if (nil? cis2) true false)
(if (or (not= (type cis1) (type cis2))
(not= (.v cis1) (.v ^CIS cis2))
(and (nil? (.cont cis1))
(not (nil? (.cont ^CIS cis2))))
(and (nil? (.cont ^CIS cis2))
(not (nil? (.cont cis1))))) false
(if (nil? (.cont cis1)) true
(recur ((.cont cis1)) ((.cont ^CIS cis2))))))))
(count [this] (loop [cis this, cnt 0] (if (or (nil? cis) (nil? (.cont cis))) cnt
(recur ((.cont cis)) (inc cnt)))))
clojure.lang.Seqable
(seq [this] (if (and (nil? v) (nil? cont)) nil this))
clojure.lang.Sequential
Object
(toString [this] (if (and (nil? v) (nil? cont)) "()" (.toString (seq (map identity this))))))
(defn primes-treeFoldingx
"Computes the unbounded sequence of primes using a Sieve of Eratosthenes algorithm modified from Bird."
[]
(letfn [(mltpls [p] (let [p2 (* 2 p)]
(letfn [(nxtmltpl [c]
(->CIS c (fn [] (nxtmltpl (+ c p2)))))]
(nxtmltpl (* p p))))),
(allmtpls [^CIS ps] (->CIS (mltpls (.v ps)) (fn [] (allmtpls ((.cont ps)))))),
(union [^CIS xs ^CIS ys] (let [xv (.v xs), yv (.v ys)]
(if (< xv yv) (->CIS xv (fn [] (union ((.cont xs)) ys)))
(if (< yv xv) (->CIS yv (fn [] (union xs ((.cont ys)))))
(->CIS xv (fn [] (union (next xs) ((.cont ys))))))))),
(pairs [^CIS mltplss] (let [^CIS tl ((.cont mltplss))]
(->CIS (union (.v mltplss) (.v tl))
(fn [] (pairs ((.cont tl))))))),
(mrgmltpls [^CIS mltplss] (->CIS (.v ^CIS (.v mltplss))
(fn [] (union ((.cont ^CIS (.v mltplss)))
(mrgmltpls (pairs ((.cont mltplss)))))))),
(minusStrtAt [n ^CIS cmpsts] (loop [n n, cmpsts cmpsts]
(if (< n (.v cmpsts))
(->CIS n (fn [] (minusStrtAt (+ n 2) cmpsts)))
(recur (+ n 2) ((.cont cmpsts))))))]
(do (def oddprms (->CIS 3 (fn [] (let [cmpsts (-> oddprms (allmtpls) (mrgmltpls))]
(minusStrtAt 5 cmpsts)))))
(->CIS 2 (fn [] oddprms)))))
(defn primes-hashmap
"Infinite sequence of primes using an incremental Sieve or Eratosthenes with a Hashmap"
[]
(letfn [(nxtoddprm [c q bsprms cmpsts]
(if (>= c q) ;; only ever equal
(let [p2 (* (first bsprms) 2), nbps (next bsprms), nbp (first nbps)]
(recur (+ c 2) (* nbp nbp) nbps (assoc cmpsts (+ q p2) p2)))
(if (contains? cmpsts c)
(recur (+ c 2) q bsprms
(let [adv (cmpsts c), ncmps (dissoc cmpsts c)]
(assoc ncmps
(loop [try (+ c adv)] ;; ensure map entry is unique
(if (contains? ncmps try)
(recur (+ try adv)) try)) adv)))
(cons c (lazy-seq (nxtoddprm (+ c 2) q bsprms cmpsts))))))]
(do (def baseoddprms (cons 3 (lazy-seq (nxtoddprm 5 9 baseoddprms {}))))
(cons 2 (lazy-seq (nxtoddprm 3 9 baseoddprms {}))))))
(deftype PQEntry [k, v]
Object
(toString [_] (str "<" k "," v ">")))
(deftype PQNode [ntry, lft, rght]
Object
(toString [_] (str "<" ntry " left: " (str lft) " right: " (str rght) ">")))
(defn empty-pq [] nil)
(defn getMin-pq [^PQNode pq]
(if (nil? pq)
nil
(.ntry pq)))
(defn insert-pq [^PQNode opq ok v]
(loop [^PQEntry kv (->PQEntry ok v), pq opq, cont identity]
(if (nil? pq)
(cont (->PQNode kv nil nil))
(let [k (.k kv),
^PQEntry kvn (.ntry pq), kn (.k kvn),
l (.lft pq), r (.rght pq)]
(if (<= k kn)
(recur kvn r #(cont (->PQNode kv % l)))
(recur kv r #(cont (->PQNode kvn % l))))))))
(defn replaceMinAs-pq [^PQNode opq k v]
(let [^PQEntry kv (->PQEntry k v)]
(if (nil? opq) ;; if was empty or just an entry, just use current entry
(->PQNode kv nil nil)
(loop [pq opq, cont identity]
(let [^PQNode l (.lft pq), ^PQNode r (.rght pq)]
(cond ;; if left us empty, right must be too
(nil? l)
(cont (->PQNode kv nil nil)),
(nil? r) ;; we only have a left...
(let [^PQEntry kvl (.ntry l), kl (.k kvl)]
(if (<= k kl)
(cont (->PQNode kv l nil))
(recur l #(cont (->PQNode kvl % nil))))),
:else (let [^PQEntry kvl (.ntry l), kl (.k kvl),
^PQEntry kvr (.ntry r), kr (.k kvr)] ;; we have both
(if (and (<= k kl) (<= k kr))
(cont (->PQNode kv l r))
(if (<= kl kr)
(recur l #(cont (->PQNode kvl % r)))
(recur r #(cont (->PQNode kvr l %))))))))))))
(defn primes-pq
"Infinite sequence of primes using an incremental Sieve or Eratosthenes with a Priority Queue"
[]
(letfn [(nxtoddprm [c q bsprms cmpsts]
(if (>= c q) ;; only ever equal
(let [p2 (* (first bsprms) 2), nbps (next bsprms), nbp (first nbps)]
(recur (+ c 2) (* nbp nbp) nbps (insert-pq cmpsts (+ q p2) p2)))
(let [mn (getMin-pq cmpsts)]
(if (and mn (>= c (.k mn))) ;; never greater than
(recur (+ c 2) q bsprms
(loop [adv (.v mn), cmps cmpsts] ;; advance repeat composites for value
(let [ncmps (replaceMinAs-pq cmps (+ c adv) adv),
nmn (getMin-pq ncmps)]
(if (and nmn (>= c (.k nmn)))
(recur (.v nmn) ncmps)
ncmps))))
(cons c (lazy-seq (nxtoddprm (+ c 2) q bsprms cmpsts)))))))]
(do (def baseoddprms (cons 3 (lazy-seq (nxtoddprm 5 9 baseoddprms (empty-pq)))))
(cons 2 (lazy-seq (nxtoddprm 3 9 baseoddprms (empty-pq)))))))
(set! *unchecked-math* true)
(def PGSZ (bit-shift-left 1 14)) ;; size of CPU cache
(def PGBTS (bit-shift-left PGSZ 3))
(def PGWRDS (bit-shift-right PGBTS 5))
(def BPWRDS (bit-shift-left 1 7)) ;; smaller page buffer for base primes
(def BPBTS (bit-shift-left BPWRDS 5))
(defn- count-pg
"count primes in the culled page buffer, with test for limit"
[lmt ^ints pg]
(let [pgsz (alength pg),
pgbts (bit-shift-left pgsz 5),
cntem (fn [lmtw]
(let [lmtw (long lmtw)]
(loop [i (long 0), c (long 0)]
(if (>= i lmtw) (- (bit-shift-left lmtw 5) c)
(recur (inc i)
(+ c (java.lang.Integer/bitCount (aget pg i))))))))]
(if (< lmt pgbts)
(let [lmtw (bit-shift-right lmt 5),
lmtb (bit-and lmt 31)
msk (bit-shift-left -2 lmtb)]
(+ (cntem lmtw)
(- 32 (java.lang.Integer/bitCount (bit-or (aget pg lmtw)
msk)))))
(- pgbts
(areduce pg i ret (long 0) (+ ret (java.lang.Integer/bitCount (aget pg i))))))))
;; (cntem pgsz))))
(defn- primes-pages
"unbounded Sieve of Eratosthenes producing a lazy sequence of culled page buffers."
[]
(letfn [(make-pg [lowi pgsz bpgs]
(let [lowi (long lowi),
pgbts (long (bit-shift-left pgsz 5)),
pgrng (long (+ (bit-shift-left (+ lowi pgbts) 1) 3)),
^ints pg (int-array pgsz),
cull (fn [bpgs']
(loop [i (long 0), bpgs' bpgs']
(let [^ints fbpg (first bpgs'),
bpgsz (long (alength fbpg))]
(if (>= i bpgsz)
(recur 0 (next bpgs'))
(let [p (long (aget fbpg i)),
sqr (long (* p p))]
(if (< sqr pgrng) (do
(loop [j (long (let [s (long (bit-shift-right (- sqr 3) 1))]
(if (>= s lowi) (- s lowi)
(let [m (long (rem (- lowi s) p))]
(if (zero? m)
0
(- p m))))))]
(if (< j pgbts) ;; fast inner culling loop where most time is spent
(do
(let [w (bit-shift-right j 5)]
(aset pg w (int (bit-or (aget pg w)
(bit-shift-left 1 (bit-and j 31))))))
(recur (+ j p)))))
(recur (inc i) bpgs'))))))))]
(do (if (nil? bpgs)
(letfn [(mkbpps [i]
(if (zero? (bit-and (aget pg (bit-shift-right i 5))
(bit-shift-left 1 (bit-and i 31))))
(cons (int-array 1 (+ i i 3)) (lazy-seq (mkbpps (inc i))))
(recur (inc i))))]
(cull (mkbpps 0)))
(cull bpgs))
pg))),
(page-seq [lowi pgsz bps]
(letfn [(next-seq [lwi]
(cons (make-pg lwi pgsz bps)
(lazy-seq (next-seq (+ lwi (bit-shift-left pgsz 5))))))]
(next-seq lowi)))
(pgs->bppgs [ppgs]
(letfn [(nxt-pg [lowi pgs]
(let [^ints pg (first pgs),
cnt (count-pg BPBTS pg),
npg (int-array cnt)]
(do (loop [i 0, j 0]
(if (< i BPBTS)
(if (zero? (bit-and (aget pg (bit-shift-right i 5))
(bit-shift-left 1 (bit-and i 31))))
(do (aset npg j (+ (bit-shift-left (+ lowi i) 1) 3))
(recur (inc i) (inc j)))
(recur (inc i) j))))
(cons npg (lazy-seq (nxt-pg (+ lowi BPBTS) (next pgs)))))))]
(nxt-pg 0 ppgs))),
(make-base-prms-pgs []
(pgs->bppgs (cons (make-pg 0 BPWRDS nil)
(lazy-seq (page-seq BPBTS BPWRDS (make-base-prms-pgs))))))]
(page-seq 0 PGWRDS (make-base-prms-pgs))))
(defn primes-paged
"unbounded Sieve of Eratosthenes producing a lazy sequence of primes"
[]
(do (deftype CIS [v cont]
clojure.lang.ISeq
(first [_] v)
(next [_] (if (nil? cont) nil (cont)))
(more [this] (let [nv (.next this)] (if (nil? nv) (CIS. nil nil) nv)))
(cons [this o] (clojure.core/cons o this))
(empty [_] (if (and (nil? v) (nil? cont)) nil (CIS. nil nil)))
(equiv [this o] (loop [cis1 this, cis2 o] (if (nil? cis1) (if (nil? cis2) true false)
(if (or (not= (type cis1) (type cis2))
(not= (.v cis1) (.v ^CIS cis2))
(and (nil? (.cont cis1))
(not (nil? (.cont ^CIS cis2))))
(and (nil? (.cont ^CIS cis2))
(not (nil? (.cont cis1))))) false
(if (nil? (.cont cis1)) true
(recur ((.cont cis1)) ((.cont ^CIS cis2))))))))
(count [this] (loop [cis this, cnt 0] (if (or (nil? cis) (nil? (.cont cis))) cnt
(recur ((.cont cis)) (inc cnt)))))
clojure.lang.Seqable
(seq [this] (if (and (nil? v) (nil? cont)) nil this))
clojure.lang.Sequential
Object
(toString [this] (if (and (nil? v) (nil? cont)) "()" (.toString (seq (map identity this))))))
(letfn [(next-prm [lowi i pgseq]
(let [lowi (long lowi),
i (long i),
^ints pg (first pgseq),
pgsz (long (alength pg)),
pgbts (long (bit-shift-left pgsz 5)),
ni (long (loop [j (long i)]
(if (or (>= j pgbts)
(zero? (bit-and (aget pg (bit-shift-right j 5))
(bit-shift-left 1 (bit-and j 31)))))
j
(recur (inc j)))))]
(if (>= ni pgbts)
(recur (+ lowi pgbts) 0 (next pgseq))
(->CIS (+ (bit-shift-left (+ lowi ni) 1) 3)
(fn [] (next-prm lowi (inc ni) pgseq))))))]
(->CIS 2 (fn [] (next-prm 0 0 (primes-pages)))))))
(defn primes-paged-count-to
"counts primes generated by page segments by Sieve of Eratosthenes to the top limit"
[top]
(cond (< top 2) 0
(< top 3) 1
:else (letfn [(nxt-pg [lowi pgseq cnt]
(let [topi (bit-shift-right (- top 3) 1)
nxti (+ lowi PGBTS),
pg (first pgseq)]
(if (> nxti topi)
(+ cnt (count-pg (- topi lowi) pg))
(recur nxti
(next pgseq)
(+ cnt (count-pg PGBTS pg))))))]
(nxt-pg 0 (primes-pages) 1))))
You may also check:How to resolve the algorithm Apply a digital filter (direct form II transposed) step by step in the Haskell programming language
You may also check:How to resolve the algorithm Random Latin squares step by step in the D programming language
You may also check:How to resolve the algorithm Comments step by step in the Babel programming language
You may also check:How to resolve the algorithm Assertions step by step in the Swift programming language
You may also check:How to resolve the algorithm Magic squares of doubly even order step by step in the Julia programming language