Sieve of Eratosthenes

Example 436

★

The haughty Eratosthenes of Cyrene will nevertheless consent to sieve prime numbers on request.

In the words of Wikipedia: "Eratosthenes of Cyrene (Greek Eρατοσθένης; 276 BC-194 BC) was a Greek mathematician, poet, athlete, geographer and astronomer." In the words of Tom Lehrer: "It's people like that who make you realise how little you've achieved in life."

A prime number is a number greater than 1 which is not a multiple of anything, so we can find the primes by starting with all the numbers and sieving out all the multiples of 2, then all the multiples of 3, and so on. Here we make our sieve of the unacceptable numbers (the "composite" or non-prime ones) first, then form a list of all the numbers, then sieve out the composites: what are left must be the primes.

Play/modify in Borogove

Play in Quixe

"Sieve of Eratosthenes"

Alexandria is a room. Eratosthenes is a man in Alexandria. "The haughty Greek mathematician, Eratosthenes, glowers at you."

Sieving is an action applying to one number. Understand "sieve [number]" as sieving.

Instead of sieving, say "You make a feeble attempt, sketching in the sand, but it goes nowhere. Eratosthenes smirks. 'I expect your friends call you gamma, then?'"

Persuasion rule for asking Eratosthenes to try sieving: persuasion succeeds.

Report Eratosthenes sieving:

let N be the number understood;

let the composites be a list of numbers;

let I be 2;

while I times I is at most N:

if I is not listed in the composites:

let J be I times 2;

while J is at most N:

add J to the composites, if absent;

increase J by I;

increment I;

sort the composites;

let the primes be a list of numbers;

repeat with P running from 2 to N:

add P to the primes;

remove the composites from the primes;

say "Eratosthenes sketches lines in the sand with the air of much practice. 'The primes up to [N] are [the primes]. The composites are [the composites].'"

Test me with "sieve 10 / eratosthenes, sieve 100".

Alexandria
The haughty Greek mathematician, Eratosthenes, glowers at you.

>(Testing.)

>[1] sieve 10
You make a feeble attempt, sketching in the sand, but it goes nowhere. Eratosthenes smirks. "I expect your friends call you gamma, then?"

>[2] eratosthenes, sieve 100
Eratosthenes sketches lines in the sand with the air of much practice. "The primes up to 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. The composites are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99 and 100."

While this could all be done more efficiently with an array, that's only because what we are sieving are numbers: sieving is a technique which can be used for non-numerical decisions, too.