Algoritme dat priemgetallen genereert

Paul

Ik geloof dat ik hier een vrij lastige vraag stel, maar er is vast iemand die het antwoord weet.

Ik zoek een zo eenvoudig mogelijk algorithme dat priemgetallen genereert. Het maakt niet uit hoe het werkt, als het maar zo weinig mogelijk rekenwerk vergt. Ik wil het namelijk in een computerprogramma verwerken.

Met welke rekenstappen kun je een programma laten berekenen: het eerstvolgende priemgetal p dat na het willekeurige getal n komt?

Hoe werkt een algorithme dat alle priemgetallen p op volgorde genereert van p=2 tot p>1e100? Of van mijn part tot p>1e1000. (Hoewel dat laatste wellicht de rekenkracht van de gemiddelde pc ontstijgt...)

(BIJVOORBEELD: voor wie het programma kent: je kunt Maple een willekeurig getal geven en dan berekent het programma het eerstvolgende priemgetal. De vraag is dus hoe dat in zijn werk gaat...)

N.B.: 1e100 staat uiteraard voor 1 x 10^100 (= een 1 met honderd nullen).

Rogier

Er is geen sluitende formule voor het n-de priemgetal, je zult dus getallen moeten blijven proberen totdat je een priemgetal hebt.

Daar komt in ieder geval een priemtest bij kijken, de simpelste is zoiets:

IsPriem(x) ?

ga alle getallen van 2 t/m wortel(x) af

als x deelbaar is door een van die getallen -> NEE (geen priem)

anders: JA (wel priem)

En een methode om het eerstvolgende priemgetal groter x te vinden:

Blijf x met 1 verhogen totdat IsPriem(x) JA oplevert.

Een methode om alle priemgetallen t/m bijvoorbeeld 1e100 berekenen is domweg alle getallen van 2 t/m 1e100 aflopen en testen. Niet de meest slimme, maar werkt beslist

In pseudo code:

IsPriem(x):

  als x<2 -> NEE

  bekijk voor y = 2 t/m sqrt(x): als x mod y = 0 -> NEE

  -> JA

GeefEerstVolgendePriemGetal(x):

  als IsPriem(x) -> return x

  -> GeefEerstVolgendePriemGetal(x+1)

In C++:

bool IsPriem( int x )

{

  if (x<2) return false;

  int wx = int(sqrt(x));

  for (int y=2; y<=wx; y++)

  {

    if (!(x%y)) return false;

  }

  return true;

}

int GeefEerstVolgendePriemGetal(x)

{

  while (!IsPriem(x)) x++;

  return x;

}

Dit is niet bepaald efficiënt, je kunt het proces bijvoorbeeld zo al twee keer zo snel krijgen door alleen te testen op deelbaarheid door 2 en verder alleen de oneven getallen van 3 t/m wortel(x). En nog eens anderhalf keer zo snel door alleen 2, 3 en verder alleen 6-vouden min één en plus één te testen.

In feite hoef je alleen op priemgetallen te testen, dus als je een lijstje van tot nu toe gevonden priemgetallen bijhoudt kun je daar op voortbouwen; zie ook de Zeef van Eratosthenes. Er zijn nog veel efficientere maar ingewikkeldere methoden om priemgetallen te vinden of te testen of een getal priem is.

Om Mersenne priemgetallen te vinden, d.w.z. priemgetallen van de vorm 2^p-1, is een zeer snel algoritme bekend, de Lucas-Lehmer test. Omdat deze test veruit het snelste is in verhouding tot de grootte van de getallen, zijn de grootste bekende priemgetallen dan ook van deze vorm.

Paul

Bedankt voor deze toch wel zeer uitgebreide en heldere uitleg! Het algorithme dat je geeft is er inderdaad eentje die in ieder geval werkt. Helaas kost 'ie toch wel erg veel rekenkracht bij grotere getallen, dus ik denk niet dat het echt een optie is. En volgens mij bestaan er wel effectievere algorithmes om priemgetallen te vinden.

De Zeef van Eratosthenes valt ook af, want Wikipedia zegt al dat dit algorithme (te) veel geheugen vergt bij grote getallen.

Een methode om de Mersenne priemgetallen te vinden is ook niet geschikt, daar lang niet alle priemgetallen Mersenne priemgetallen zijn.

Maar om even terug te komen op het algorithme dat we al hebben, de efficiëntere versie zou er dus ongeveer zo uitzien in C++?:

Code: Selecteer alles

bool IsPriem( int x ) 

{ 

  if (x<2) return false; 

  for (int y=2; y<=3; y++)

  {

    if (!(x%y)) return false;

  }

  int wx = int(sqrt(x));

  int y=5

  while (y<=wx) 

  { 

    if (!(x%y)) return false;

    y = y + 2;

    if (!(x%y)) return false;

    y = y + 4;

  } 

  return true; 

} 

int GeefEerstVolgendePriemGetal(x) 

{ 

  while (!IsPriem(x)) x++; 

  return x; 

}

Nu schrijf ik zelf niet in C++ maar in Java. Ik heb nog een vraagje over de volgende regel. Ik begrijp wel wat hij doet maar hoe zit het precies met die voorwaarde? Wat doet dat uitroepteken? Moet er niet ergens =0 staan? % is mod toch?:

Code: Selecteer alles

    if (!(x%y)) return false;

Hoe dan ook, ik zoek nog steeds een slim algorithme dat alle priemgetallen vindt.

Rogier

Maar om even terug te komen op het algorithme dat we al hebben, de efficiëntere versie zou er dus ongeveer zo uitzien in C++?

Yep, correct.

Nu schrijf ik zelf niet in C++ maar in Java. Ik heb nog een vraagje over de volgende regel. Ik begrijp wel wat hij doet maar hoe zit het precies met die voorwaarde? Wat doet dat uitroepteken? Moet er niet ergens =0 staan? % is mod toch?:

% is modulo ja, ik had ook if ((x%y)==0) kunnen doen (let op dubbele =).

Die ! betekent zoiets als "not", en in C++ is een expressie waar als er niet nul uit komt, dus (!(x%y)) is waar als er uit (x%y) nul komt. Kwestie van gewoonte, ik had voor de duidelijkheid hier misschien beter gewoon met nul kunnen vergelijken

Hoe dan ook, ik zoek nog steeds een slim algorithme dat alle priemgetallen vindt.

Zie ook: http://mathworld.wolfram.com/PrimalityTest.html

Daar staan er een hele rits bij See Also. Die gaan echter meer code kosten dan dat van hierboven

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Algoritme dat priemgetallen genereert

Algoritme dat priemgetallen genereert

Re: Algoritme dat priemgetallen genereert

Re: Algoritme dat priemgetallen genereert

Re: Algoritme dat priemgetallen genereert