Sieve of Eratosthenes: Difference between revisions

=={{header|BQN}}==

A more efficient sieve (primes below one billion in under a minute) is provided as <code>PrimesTo</code> in bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn].

<lang bqn>Primes ← {

𝕩≤2 ? ↕0 ; # No primes below 2

p ← 𝕊⌈√n←𝕩 # Initial primes by recursion

b ← 2≤↕n # Initial sieve: no 0 or 1

E ← {↕∘⌈⌾((𝕩×𝕩+⊢)⁼)n} # Multiples of 𝕩 under n, starting at 𝕩×𝕩

/ b E⊸{0¨⌾(𝕨⊸⊏)𝕩}´ p # Cross them out

}</lang>

{{out}}

<lang bqn> 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 ⟩

≠∘Primes¨ 10⋆↕7 # Number of primes below 1e0, 1e1, ... 1e6

⟨ 0 4 25 168 1229 9592 78498 ⟩