Zeef van Eratosthenes

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Animatie van de toepassing van de zeef van Eratosthenes op de gehele getallen van 1 t/m 120.

De zeef van Eratosthenes (bibliothecaris van Alexandrië vanaf ca. 240 v.Chr.) is een al zeer lang bekend algoritme om priemgetallen te vinden. Deze elegante methode is vooral efficiënt wanneer hij wordt gebruikt voor de kleinere priemgetallen. De methode vergt echter het bijhouden van alle getallen kleiner dan de gebruikte bovengrens, wat naarmate de te bepalen priemgetallen groter worden een steeds groter nadeel wordt.

Methode[bewerken]

  1. Maak een gesorteerde lijst van alle getallen van 2 tot een zelf te kiezen maximum.
  2. Kies het kleinste getal uit de lijst.
  3. Streep alle veelvouden van het gekozen getal door (maar niet het getal zelf).
  4. Kies het volgende getal uit de lijst en ga verder met stap 3.

De getallen die op deze manier overblijven zijn alle priemgetallen tot het maximum.

De procedure kan op enkele manieren versneld worden.

  • Het heeft geen zin in stap 4 een getal te kiezen dat al doorgestreept is, want alle veelvouden daarvan zijn al doorstreept.
  • Men kan met doorstrepen beginnen met het kwadraat van het gekozen getal. Alle kleinere veelvouden zijn al doorstreept.
  • Is het gekozen getal groter dan de wortel uit het maximum, dan is de procedure voltooid.

Voorbeeld[bewerken]

We zoeken bijvoorbeeld de priemgetallen tot en met 30. We beginnen met de lijst van 2 tot en met 30 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
In de eerste ronde strepen we de veelvouden van 2 weg, te beginnen met 22, dus 4 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Daarna gaan we verder met de veelvouden van 3, te beginnen met 32, dus 9 (de grijze vakjes zijn veelvouden van 3 die minder zijn dan 9, deze kunnen we negeren) 2 3 5 7 11 13 17 19 23 25 29
Het getal 4 is al weggestreept, dus gaan we verder met veelvouden van 5, te beginnen met 52, dus 25. 2 3 5 7 11 13 17 19 23 29
Het volgende getal is 7, dus moeten we nu de veelvouden van 7 wegstrepen, te beginnen met 72, maar dat is meer dan 30, dus we kunnen nu stoppen. Wat we overhouden zijn de priemgetallen met een maximum van 30: 2 3 5 7 11 13 17 19 23 29

Met de computer[bewerken]

Het volgende computerprogramma gebruikt de zeef van Eratosthenes om priemgetallen te genereren. Het is geschreven in de programmeertaal C.

  /* opmerking:
   alle veelvouden k*i van i met k kleiner dan i werden al weggestreept 
   als veelvoud van k (of beter: van k's kleinste priemdeler),
   dus mag de ondergrens van j inderdaad i*i ipv 2*i zijn.
  */
 
  #include <stdio.h>
  #include <stdlib.h>
 
  int main(int argc, char **argv){
    unsigned long long i,j,maxpriem = (argc == 2 ? atoll(argv[1]) : 100);
    char priemen[maxpriem + 1];
 
    for(i = 2; i <= maxpriem; i++) 
      priemen[i] = 1;                  /* Alle getallen op 1 instellen */
 
    priemen[0]= priemen[1]= 0;         /* 0 en 1 uitsluiten. */
    for(i = 2; i * i < maxpriem; i++)
      if(priemen[i] == 1)              /* Als een getal een priem is: */
        for(j = i * i; j <= maxpriem; j += i) 
          priemen[j] = 0;              /* Streep dan alle veelvouden weg. (zie opm bovenaan) */
 
    for(i = 0; i <= maxpriem; i++)     /* Resultaten weergeven */
      if(priemen[i] == 1)
        printf("%llu ",i);
    putchar('\n');
 
    return 0;
  }

Voorbeeld in de programmeertaal PHP:

    //Maximum getal
    $maxprime = 100;
 
    //Alle nummers 1
    for ($a = 0; $a <= $maxprime; $a++)
        $primes[$a] = 1;
 
    //0 en 1 doen niet mee
    $primes[0] = 0;
    $primes[1] = 0;
 
    //Priemgetallen zoeken
    for ($a = 2; $a * $a < $maxprime; $a++)
        if ($primes[$a] == 1)
            for ($b = $a * $a; $b <= $maxprime; $b += $a)
                $primes[$b] = 0; //Verwijder de veelvouden
 
    //Priemgetallen weergeven
    for ($c = 0; $c <= $maxprime; $c++)
        if ($primes[$c] == 1)
            echo $c ."\n";

Voorbeeld in de programmeertaal Haskell.

  priemgetallen :: [Integer]    
  -- priemgetallen is een (oneindige) lijst van integers die wordt verkregen door 
  -- de zeef toe te passen op de (oneindige) lijst van natuurlijke getallen beginnend met 2.
  -- hierbij is de zeef op een lijst getallen gedefinieerd als de lijst bestaande uit het 
  -- eerste getal uit de oorspronkelijke lijst gevolgd door de zeef toegepast op dezelfde lijst,
  -- waar echter alle veelvouden van het eerste getal uit zijn verwijderd. 
 
  priemgetallen = zeef [2..]   
    where zeef (p:xs) = p : zeef [x | x<-xs, x `mod` p /= 0]

Voorbeeld in de programmeertaal Visual Basic

    Private SUB Form_Load()
        CONST ZoekenTotGetal = 100                          'Of tot welke waarde dan ook
        DIM filter(ZoekenTotGetal) AS Boolean               'alle getalleen tot ZoekenTotGetal
 
        FOR I = 2 TO ZoekenTotGetal
            IF filter(I) = False THEN                       'als getal niet uitgefilterd is
                PRINT I                                     'dan is het priem
                FOR J = I TO ZoekenTotGetal STEP I          'en filter je alle getallen met priemfactor eruit
                  filter(J) = True
                NEXT
            END IF
        NEXT
    END SUB

Voorbeeld in de programmeertaal Java

import java.util.BitSet;
 
public class PrimeBitSet extends BitSet {
 
	public PrimeBitSet(int size) {
		super(size);					// nieuwe bitset, allen niet-priem
		set(2, size);					// alles vanaf 2 is priem
		int sqrt = (int)Math.sqrt(size);		// bovenlimiet bepalen
		for (int i = 0; (i = nextSetBit(i)) != -1 && i <= sqrt; i++) {	// volgende priem vinden
			for (int j = i * i; j < size; j += i)	// meervouden van gevonden priem
				clear(j);			// wissen vanaf priem ^ 2
		}
	}
 
	public static void main(String[] args) {
		System.out.println(new PrimeBitSet(1000));	// alle priemgetallen tonen tot 1000
	}
}

Voorbeeld in de programmeertaal Python

class Sieve(object):
    def __init__(self, maxPrime):
        allNumbers = range(0, maxPrime+1) # maak een originele lijst
        allNumbers[1] = 0                              # 1 is geen priemgetal
        for i in xrange(len(allNumbers)):
            if allNumbers[i] != 0:                       
                for m in xrange(i*i, maxPrime+1, i):
                    allNumbers[m] = 0                  # schrap alle veelvouden
 
        c = allNumbers.count(0)                     # verwijder de nullen uit de lijst
        for i in xrange(c): 
            allNumbers.remove(0)
 
        self.primes = allNumbers
 
    def printPrimes(self):
        for i in self.primes:
            print i

Voorbeeld in de programmeertaal JavaScript opgenomen in een html-pagina

  <html>
  <head>
 
  <script language="javascript" type="text/javascript">
    function getPriemen() {
 
        var max = document.getElementById("maxpriem").value;
        var priemLijst = "";
 
        // initialiseer een Array van alle getallen van 2 to max
        // wijs 1 toe, hetgeen voorlopig betekent 'mogelijk een priem'
        var getallen = new Array();
        for (var i = 2; i <= max; i++) {
            getallen[i] = 1;
        }
 
       // Zoek de niet-priemen: ken 0 toe aan elke niet-priem
       for (var i = 2; i*i < max; i++) {
           if (getallen[i] == 1) {
               for (var j = i * i; j <= max; j += i) {
                       getallen[j] = 0; // Getal is een veelvoud, dus geen priem: wijs 0 toe.
               }
           }
       }
 
       // ieder getal dat nu nog op 1 staat is inderdaad een priem.
       for (var i = 0; i <= max; i++) {
           if (getallen[i] == 1) {
               priemLijst += i + " ";
           }
       }
 
       return priemLijst;
 
    }
  </script>
 
  <title>Zeef van Eratosthenes</title>
  </head>
  <body>
    <h2><a href="javascript:alert(getPriemen())">Bereken priemen tot </a> <input id="maxpriem" value="10" /></h2>
  </body>
  </html>