Springen naar inhoud

Algoritme dat priemgetallen genereert


  • Log in om te kunnen reageren

#1

Paul

    Paul


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 22 maart 2005 - 22:15

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).

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 22 maart 2005 - 23:08

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 :shock:

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 2p-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.
In theory, there's no difference between theory and practice. In practice, there is.

#3

Paul

    Paul


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 23 maart 2005 - 17:08

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++?:

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?:

   if (!(x%y)) return false;
Hoe dan ook, ik zoek nog steeds een slim algorithme dat alle priemgetallen vindt.

#4

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 23 maart 2005 - 17:23

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.wol...malityTest.html
Daar staan er een hele rits bij See Also. Die gaan echter meer code kosten dan dat van hierboven :shock:
In theory, there's no difference between theory and practice. In practice, there is.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures