[WI] Klein vraagje over priemgetallen.

[Rob]

Tijdje terug moest ik een programmatje schrijven dat de eerste 1000 priemgetallen berekend. Ik heb 't op een redelijk naïve (lees, alle getallen tussen 1 en n-1 delen door n en kijken of de modulus gelijk was aan 0) manier opgelost aangezien ik weinig zin had in veel coden en nog genoeg andere dingen te doen had. :p

Nu wil ik als commentaar mogelijke optimalisaties erbij zetten en één daarvan was mijn suggestie om maar tot en met n/2 te kijken met de volgende redenatie:

Stel: Ik wil weten of n priem is.
Bij de getallen die ik onderzoek en die tussen 1 en n/2 liggen, kan er modulus 0 uitkomen (en dus is n niet priem).
Als mod(n/2) 0 is, dan is het getal niet priem (en de uitkomst 2).

Voor alle getallen die tussen n/2 + 1 en n-1 liggen, ligt de uitkomst dus altijd tussen 2 en 1 (maar zal er nooit gelijk aan zijn). En dus is n priem.

Maar ik weet niet 100% zeker of dit geldt. Het is zeker niet de beste optimalisatie (aangezien tot en met √(n) checken effectiever is), maar het lijkt mij wel leuk erbij te hebben in het commentaar. :p

[WelVrolijk]

Je redenatie klopt wel.
Maar met vrijwel dezelfde redenatie kun je de zaak begrenzen op wortel n.
Dan hoef je maar een stuk of 30 getallen te testen i.p.v. ongeveer 500.

Een andere (bekende, voor de hand liggende) optimalisatie is om (zodra je voorbij de 2 bent) alleen nog oneven getallen te testen.
Daarmee breng je het terug van ongeveer 500 naar ongeveer 250 (of van ongeveer 30 naar 16).
Dat is ook makkelijk uit te leggen.

Of (als variant op de vorige) zodra je voorbij de 3 bent, alleen nog 6-vouden+1 en 6-vouden+5.
Daarmee breng je het terug van ongeveer 250 naar ongeveer 170, of van 16 naar 10.
Dat lijkt niet echt de moeite waard, omdat de uitleg al wat ingewikkelder wordt.

---

Trouwens leuk dat je niet gewoon de zeef van Erastosthenes heb gekozen.
Dat zullen de meeste medestudenten waarschijnlijk hebben gedaan.
Vaak is de keus voor een simpeler algoritme beter.

[Rob]

Ach, de zeef werkt alleen maar als je weet tot welke n je moet kijken. :p Ik ben er wel mee bekend.
Mijn optimalisatie was meer gefocused op "Ik weet niet tot hoever ik moet, maar ik wil alleen de eerste n priemgetallen weten".

De wortel n methode ben ik al bekend mee; Die had ik dan ook al toegevoegd aan de lijst. Die zegt, volgens mij, dat als je n wilt weten, dat je alleen maar tot √(n) hoeft te gaan, omdat als n composiet is, een van de termen kleiner of gelijk is aan √(n)

De andere methode die ik nog had, was "als het getal eindigt op 0, 2, 4, 6 of 8, is het een tweevoud. Eindigt het op 5 of 0, is het een vijfvoud. Dus die kunnen overslagen geworden".

Maar die van "niet verder kijken dan n/2" schoot me op een willekeurig moment binnen, eigenlijk. Dus ik was benieuwd of ik goed dacht. :p

Maar in de regel is sqrt<n/2, dus maakt het niet zo veel uit.

Als je wilt weten of getal n (zorg voor n = 1 of 5 mod 6) dan hoef je n alleen te delen door de priemgetallen t/m √n. Als n deelbaar zou zijn door een getal r = pq, waarbij p & q priem zijn, dan is n ook deelbaar door p & q. Dus het is niet nodig om n te delen door samengestelde getallen.

Dit werkt natuurlijk goed als je met kleine getallen werkt, maar als je verder gaat is het misschien een idee om bij elk getal eerst een paar fermat proeven te doen.

Naja veel succes ermee,
~