Extensible prime generator: Difference between revisions

=={{header|BQN}}==

This implementation uses a simple segmented sieve similar to the one in [[Sieve of Eratosthenes#BQN|Sieve of Eratosthenes]]. In order to match the task most closely, it returns a generator function (implemented as a closure) that outputs another prime on each call, using an underlying <code>primes</code> array that's extended as necessary. Working with one prime at a time is inefficient in an array language, and the given tasks can be solved more quickly using functions from bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn], which also uses a more complicated and faster underlying sieve.

<lang bqn># Function that returns a new prime generator

PrimeGen ← {𝕤

i ← 0 # Counter: index of next prime to be output

primes ← ↕0

next ← 2

Sieve ← { p 𝕊 i‿n:

E ← {↕∘⌈⌾(((𝕩|-i)+𝕩×⊢)⁼)n-i} # Indices of multiples of 𝕩

i + / (1⥊˜n-i) E⊸{0¨⌾(𝕨⊸⊏)𝕩}´ p # Primes in segment [i,n)

}

{𝕤

{ i=≠primes ? # Extend if required

next ↩ ((2⋆24)⊸+ ⌊ ט) old←next # Sieve at most 16M new entries

primes ∾↩ (primes(⍋↑⊣)√next) Sieve old‿next

;@}

(i+↩1) ⊢ i⊑primes

}

}

_w_←{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} # Looping utility for the session below</lang>

{{out}}

<lang bqn> pg ← PrimeGen@

(function block)

PG¨ ↕20

⟨ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ⟩

{p←↕0 ⋄ PG∘{ p∾↩𝕩}_w_(<⟜ 150) PG _w_(<⟜ 100)0 ⋄ p}

⟨ 101 103 107 109 113 127 131 137 139 149 ⟩

{p←0 ⋄ PG∘{𝕤⋄p+↩1}_w_(<⟜8000) PG _w_(<⟜7700)0 ⋄ p}

30

(PrimeGen@)⍟1e4 @ # Reset the count with a new generator

104729</lang>