Over de zeef van Eratosthenes - de oudste priemzeef
De zeef van Eratosthenes vindt alle priemgetallen tot een grens zonder een enkele deling. Je telt alleen: streep na 2 elk tweede getal weg, na 3 elk derde, enzovoort. Wat overblijft, zijn de priemgetallen. Meer dan tweeduizend jaar later is het nog steeds een van de snelste manieren om ze op te sommen.
Eratosthenes van Cyrene
Eratosthenes leefde van ongeveer 276 tot 194 v.Chr. en was hoofd van de grote bibliotheek van Alexandrië. Hij is vooral bekend omdat hij de omvang van de aarde bepaalde uit de lengte van schaduwen in twee steden. De zeef is naar hem genoemd omdat Nicomachus van Gerasa hem als zijn methode beschreef in de Inleiding tot de rekenkunde, geschreven rond 100 n.Chr.
Zo werkt de zeef
Schrijf de getallen van 2 tot N op. Het eerste getal, 2, is een priemgetal: streep 4, 6, 8 en elk ander veelvoud van 2 weg. Het volgende getal dat over is, 3, is een priemgetal: streep 9, 12, 15 enzovoort weg. Ga zo door met 5, 7 en de volgende getallen die over zijn. Een getal dat nooit wordt weggestreept, heeft geen kleinere deler, dus het is een priemgetal.
Stoppen bij de wortel
Elk samengesteld getal tot N heeft een priemfactor die niet groter is dan de wortel van N. Zodra p² groter is dan N, valt er dus niets meer weg te strepen. Voor de priemgetallen tot 100 heb je alleen 2, 3, 5 en 7 nodig, en voor 1000 de priemgetallen tot 31.
Hoe snel is het?
De zeef heeft ongeveer N log log N stappen nodig, en dat groeit maar een beetje sneller dan N zelf. Computers gebruiken hem nog steeds, vaak in stukken als gesegmenteerde zeef, om priemgetallen tot in de miljarden op te sommen. Om te testen of één groot getal een priemgetal is, zijn andere methoden sneller.
Veelgestelde vragen
Wie heeft de zeef van Eratosthenes bedacht?
Hij is genoemd naar Eratosthenes van Cyrene, een Griekse geleerde uit de derde eeuw v.Chr. De oudste geschreven beschrijving is van Nicomachus van Gerasa, rond 100 n.Chr.
Waarom begint de zeef bij p² met wegstrepen?
Elk kleiner veelvoud van p heeft een kleinere priemfactor, dus een kleiner priemgetal heeft het al weggestreept.
Hoeveel priemgetallen zijn er onder 1000?
Er zijn 168 priemgetallen onder 1000. Het grootste is 997.
Gerelateerde gereedschappen
Zeef van Eratosthenes
Kijk hoe de zeef van Eratosthenes de priemgetallen tot 100, 200, 500 of 1000 vindt. Elk priemgetal streept zijn veelvouden weg in een eigen kleur, stap voor stap.
Ulam-spiraal
Teken de Ulam-spiraal in je browser. Markeer de priemgetallen, lees de kwadratische formule van elke diagonaal en open Eulers ononderbroken reeks van 40 priemgetallen.
De Ulam-spiraal
Hoe de spiraal van Stanisław Ulam uit 1963 de gehele getallen op een vierkant raster legt, waarom priemgetallen zich op kwadratische diagonalen verzamelen en waar Eulers veertig priemgetallen liggen als de spiraal bij 41 begint.
Het vermoeden van Collatz
Verken het Collatz-3n+1-probleem in je browser. Volg hagelsteenreeksen, laat een geometrische Collatz-boom groeien en zoom in op de continue Collatz-fractal.
Klaar om het te proberen?
Open PictorX in uw browser - geen installatie, geen creditcard vereist om te starten.
Probeer de zeef van Eratosthenes