The Sieve of Eratosthenes — a dart

THE TECHNIQUE write 2..N · strike each prime’s multiples · survivors are prime

List the numbers 2..N. Take the smallest un-struck number — it is prime. Strike all its multiples. Repeat with the next survivor. Nothing left standing was ever a multiple, so it must be prime. The elegance: no number is ever divided — to reach the next multiple you only add p again. live demo

for p = 2 .. N: if p not struck: // p is prime for m = p*p, p*p+p, ...: // start at p² (smaller multiples strike m // were struck by smaller primes)

N =

Press sweep to watch each prime strike its multiples.

0primes found

0strikes (additions)

0divisions used

7 current prime 21 being struck 9 struck (composite) — the divisions used box stays 0 for the whole sieve: it is pure addition.

HISTORY & CREDIT credit where it is due

The method is named for Eratosthenes of Cyrene (c. 276–194 BC), the polymath who ran the Library of Alexandria and first measured the Earth’s circumference. The sieve is dated to roughly 240 BC. cited

c. 240 BC · Eratosthenes is credited with the method — but no surviving text of his own describes it.
early 2nd c. AD · Nicomachus of Gerasa, Introduction to Arithmetic — the earliest known reference, some ~350 years later. It names Eratosthenes as the source.
the honest catch · Nicomachus’ version sieves by odd numbers, not by primes — so the exact procedure we teach today is a later refinement of what he recorded.

So the attribution is real but thin: it rests on a single second-hand source describing a slightly different procedure. Historians accept the name; the primary evidence does not survive. That is worth stating plainly rather than papering over. open

One thing is not in doubt: the property Nicomachus already saw — “only additions are needed, no multiplications or divisions” — is exactly why the sieve is still fast (O(n log log n)) two millennia on.

RECOMMEND FOR I-13 the sieve wants an array; primality now runs

Two findings, both measured on the live H1.1 compiler — not asserted.

Angle 1 — the sieve proper is a wall. The whole method needs a mark-buffer: an array of flags, one per number, to remember what has been struck. I-13 has no array type. Proven:

i13 check sieve.i13 => 1:12 E0001 unexpected character `[` 1:23 E0001 unexpected character `]` (no array literal; the strike-buffer cannot be declared) i13 run arith.i13 => q = 3.4 (`/` is f64 division — no truncation, no int index)

Angle 2 — but trial-division primality RUNS. You don’t need the array to test one number: d divides p iff p % d == 0. The language panel just added % — so I wrote a real recursive trial-division test in I-13 and ran it:

def check(I p, I d) { if d * d > p { -> 1 } // no divisor up to √p: prime I m <- p % d if m == 0 { -> 0 } // d divides p: composite -> check(p, d + 1) } def is_prime(I p) { if p < 2 { -> 0 } -> check(p, 2) }

i13 run mod.i13 => 17 % 5 = 2 (% is LIVE in H1.1) i13 run prime.i13 => is_prime(7)=1 is_prime(9)=0 is_prime(97)=1 is_prime(1)=0 is_prime(2)=1 (RUN OK · 339 steps · call depth 10)

Recommend — KEEP %. Modulo is the one primitive that turns divisibility into a test, and the panel added it the cheapest honest way: a new BinOp discriminant, spending zero new alphabet symbols (it rides the existing BinOp seat alongside + − * /). It is still a branch proposal in this build — land it. With it, the whole trial-division family of number theory becomes expressible.
Do NOT add arrays for this. The sieve’s speed comes from a mutable mark-buffer, and that is a genuinely bigger ask than one discriminant — an array type touches the type system, the VM heap, and the counted-alphabet purity all at once. The honest trade: I-13 buys per-number primality for free (via %), but the batch sieve stays out of reach until arrays exist. For a language whose identity is a counted 13-symbol alphabet and an f64-only Constant, testing a prime is worth the discriminant; caching a million of them is not worth the array — yet.