Zeef van Eratosthenes


De zeef van Eratosthenes is een snelle manier om alle priemgetallen tot een bepaalde grens vast te stellen.

Een priemgetal is een geheel getal groter dan 1 dat alleen deelbaar is door 1 en zichzelf. Het getal 1 is geen priemgetal, maar heet een eenheid. Het gevolg van deze definitie is dat elk positief geheel getal op unieke wijze te schrijven is als product van zijn priemdelers (factoren).

Kies een getal n, de grootte van de zeef is dan nxn en bevat alle getallen van 1 tot en met nxn. Het eerste priemgetal waarmee gezeefd wordt is 2. Alle veelvouden van 2 worden weggestreept (uitgezeefd). Het eerstvolgende getal dat nog niet is weggestreept is 3. Vervolgens streep je de veelvouden van 3 weg. Dit proces herhalen totdat het eerstvolgende priemgetal waarvan je de veelvouden wilt wegstrepen groter is dan n. Het aantal priemgetallen tot en met n wordt dus gebruikt om te zeven.

Het resultaat is dat je alle priemgetallen tot en met nxn overhoudt.

De zeef kun je gebruiken om alle priemdelers van een getal tot en met nxnxnxn te vinden. Dus zeven met de priemgetallen tot en met n, levert een zeef op waarmee alle factoren gevonden kunnen worden van getallen tot en met nxnxnxn.

Alhoewel dit op het eerste gezicht dus een zeer efficiŽnte methode lijkt, zijn de getallen in de 'echte wereld' waarvan moet worden vastgesteld of ze priem zijn (of samengesteld) zeer groot. Het is dan vaak niet mogelijk om een zeef te construeren die groot genoeg is (het kost teveel rekentijd/ opslagruimte). Voor dit soort situaties zijn andere technieken beschikbaar; het vaststellen of een getal priem is of niet, dan wel het vinden van de priemdelers (als je al hebt vastgesteld dat het getal niet priem is) wordt nu uitbesteed aan 2 gescheiden technieken, vaak gespecialiseerd op getallen van een bepaalde vorm.