🚀 go-pugleaf

On Tue, 23 Oct 2001 19:19:44 GMT,
Roel Schroeven <x3jmyi0yrrn3h001@sneakemail.com> wrote:
>In article <qggB7.804$yZ.177@afrodite.telenet-ops.be>, "Regus"
><regus@pandora.be> wrote:
>
>> Ik moet in pascal alle priemgetallen tussen 1 en 100 hebben. Kan iemand
>> mij verderhelpen?
>
>Daar bestaat een algorithme voor, het algorithme van Euclides als ik me
>niet vergis. Dat gaat als volgt.
>
>1. Maak een lijst van de getallen van 2 tot 100 (vanaf 2 omdat 1 toch
>geen priemgetal is, en het maakt het algorithme eenvoudiger), en onthoudt
>op de een of andere manier of het getal in kwestie priem is of niet:
>"var priemlijst: array[2..100] of boolean"
>voldoet prima, als mijn kennis van Pascal-syntax nog klopt).
>2. Initialiseer alle getallen in die lijst als zijnde priem:
>for i := 2 to 100 do priemlijst[i] := true;
>3. Loop over alle getallen in de lijst. Als het getal in kwestie niet
>priem is, ga je direct naar het volgende. Als het wel priem is, duidt je
>alle veelvouden van dat getal aan als zijnde niet priem. Je kan ineens
>ook het betreffende getal uitvoeren.
>
>for i := 2 to 100 do begin
>  if priemlijst[i] then begin
>    WriteLn(i);
>    j := 2 * i;

Vervang bovenstaande lijn door.

     j := i * i;

Je kan al direct naar het kwadraat van het nieuwe priemgetal
springen om de heel eenvoudige reden dat op dit moment alle
reeds kleinere priemgetallen gevonden zijn en hun veelvouden
geschrapt. Alle getallen die een veelvoud zijn van het nieuwe
gevonden priemgetal maar kleiner dan het kwadraat zijn dus
ook een veelvoud van een kleiner priemgetal en dus reeds
geschrapt.

>    while j < 100 do begin
>      priemlijst[j] := false;
>      j := j + i;
>    end;
>  end;
>end;
>
>Er zal nogal wat haar op de syntax staan vrees ik, maar het algorithme
>zou wel moeten kloppen, en is efficienter dan de andere oplossingen die
>ik gezien heb. 't Is trouwens beter als je die 100 in een constante
>steekt, dan kan je het programma gemakkelijk aanpassen om de
>priemgetallen tussen bijv. 2 en 10000 te zoeken. Je moet wel altijd bij 2
>beginnen!
>
>-- 
>Roel Schroeven
>x3jmyi0yrrn3h001@sneakemail.com (anti-spam email address from sneakemail.com)
>
>"Don't blame me if there are bugs. Blame the cute, furry one." - Rusty Russell