Sieve of Eratosthenes: Difference between revisions
Add BQN
(Eratosthenes for beginners) |
(Add BQN) |
||
Line 2,103:
@ ^ p3\" ":<
2 234567890123456789012345678901234567890123456789012345678901234567890123456789
=={{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 ⟩
=={{header|Bracmat}}==
| |||