Lijst van Priemgetallen

[tranoniempjes]

Beste forumleden,
 
Ik ben op zoek naar een lijst van de eerste 1.000.000.000 priemgetallen.
 
Jammer genoeg gaan de lijsten meestal niet verder dan de eerste 10.000 priemgetallen. hebben jullie misschien ergens een andere lijst gezien?                                                  Zo ja hoor ik het graag.
 
Alvorens bedankt.

[klazon]

Ik ken zo'n lijst niet, maar ik vraag me wel af wat je er mee wil gaan doen. Een lijst van 10000 is al een groot blad vol, en 1.000.000.000 is 100.000 keer zo veel. Dat is een hele boekenkast vol.

[Benm]

Tja, je hoeft het niet uit te printen natuurlijk, die lijst zou je kunnen oplslaan op een bluray disk oid. 
 
Anderzijds denk ik niet dat er veel nut is voor zo'n lijst, in die orde ga je gewoon zoeken naar een priemgetal. Voor encryptie gebruikt men bijv 256 bits priemgetallen, in base-10 notatie zouden die in de buurt van 120 cijfers lang zijn, en er zijn er VEEL... veel meer dan een miljard. 

[barthol]

Ik denk ook dat er niet veel nut is voor zo'n lijst, maar als je niets te doen hebt en je verder niet van plan bent om zo'n lijst te publiceren, kan je zo'n lijst natuurlijk zelf gaan genereren.

Bij het hoogste priemgetal dat je kent, noem het getal "x" zijn automatisch alle priemgetallen lager dan het kwadraat van x te bepalen. Waardoor je dus weer hogere x kan bepalen. Je zou je computer met een programmaatje er even mee bezig kunnen houden en wat computergeheugen er mee kunnen vullen.

Maar het heeft denk ik dus niet meer nut dan het nut ervan wat jezelf nodig hebt.

[Benm]

Er zijn gelukkig wel efficientere manieren dan 1 voor 1 checken of het volgende getal priem is dan domweg proberen te factoreren. 
 
Voor getallen in de orde van een miljard is het geen probleem om het 'met de botte bijl' te doen, het zijn 30.000 delingen om te testen of iets dergelijks, millisecondenwerk voor een moderne cpu. 
 
Maar als het gaat om getallen van 256 bits lang ligt dat toch iets anders, die zouden 2^128 operaties kosten om te testen voor priem, en dat gaat wel even duren

[Bart23]

Sinds wanneer moet iets nut hebben om interessant te zijn?

Voor lijsten met priemgetallen:

https://primes.utm.edu/lists/small/

[barthol]

Er zijn gelukkig wel efficientere manieren dan 1 voor 1 checken of het volgende getal priem is dan domweg proberen te factoreren.

Nee je gaat niet 1 voor 1 elk getal checken.

Alle priemgetallen hoger dan 3 voldoen aan 6n-1 of 6n+1

Maar p*(6n-1) en p*(6n+1) waarbij p een priemgetal is, en wat je pas vanaf p^2 hoeft te checken, zijn de uitzonderingen van 6n-1 en 6n+1 die uiteraard geen priemgetallen zijn.

[AWeeda]

Inderdaad 6n-1 en 6n+1 zijn de getallen die op deelbaarheid getest moeten worden.
Je hoeft daarbij niet alle mogelijke delers te proberen. Testen op eerder gevonden priemgetallen tot maximaal de wortel van het te testen getal is voldoende.
dus om te test of 101 priem is hoef je alleen 3, 5 en 7 te testen.
1 miljard priemen heb je dan zo te pakken.

[Benm]

Formeel ook 2, al is dat voor mensen wel heel gemakkelijk

[Back2Basics]

@tranoniempjes: vanwaar de belangstelling?

En één miljard priemgetallen lijkt me wel veel. Zijn er wel zoveel bekend? Wat dat betreft: hoewel zijn er nu eigenlijk bekend?

[Benm]

Een miljard lijkt veel, maar is het niet. 
 
Priemgetallen van 1024 of zelfs 2048 bits worden continu gebruikt voor encryptie - decimaal zijn dat getallen van ca 300 cq 600 cijfers. Een priemgetal van die lengte vinden is geen enkel probleem, je hebt het waarschijnlijk zojuist met je eigen computer gedaan om je https verbinding op te zetten. 
 
Met de priem-functie kun je inschatten hoeveel van dergelijke nummers er grofweg bestaan, maar ze zijn niet interessant genoeg om bij te houden in een lijstje of iets dergelijks. 
 
Een beetje voor het perspectief: het grootste priemgetal dat we nu kennen is een mersenne priem dat decimaal dik 23 miljoen cijfers lang is,  daarbij vergeleken zijn die cryptografische priemgetallen miniem.