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:

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
}


   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 ⟩