| |
sieve←{
b←⍵⍴{∧⌿↑(×/⍵)⍴¨~⍵↑¨1}q←2 3 5
b[⍳6⌊⍵]←(6⌊⍵)⍴0 0 1 1 0 1
49≥⍵:b
p←(≢q)↓{⍵/⍳⍴⍵}∇⌈⍵*0.5
m←1+⌊(⍵-1+p×p)÷2×p
b ⊣ p {b[⍺×⍺+2×⍳⍵]←0}¨ m
}
+/ sieve 1e9
50847534
| • |
Mark as not-prime multiples of each prime less
than ⍵*0.5 .
|
| • |
Multiples of 2 3 5
are marked by initializing b
with ⍵⍴{∧⌿↑(×/⍵)⍴¨~⍵↑¨1}2 3 5
rather than with ⍵⍴1 .
|
| • |
Subsequently, only odd multiples of
primes > 5
need to be marked.
|
| • |
Multiples of a prime to be marked
can start at its square.
|
|