[C++] Priemgetallen berekenen

[Xof]

Ik heb een progje geschreven die de priemgetallen berekend, maar nu zit ik met een probleem...
Ik gebruik unsigned long en die gaat maar tot 4294967295

code:

Voer een getal in:
4294967295

Deelbaar door:
3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 
65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645,
16711935, 16843009, 50529027, 84215045, 252645135, 286331153,
858993459, 1431655765

4294967295 is geen priemgetal

code:

Voer een getal in:
4294967296

0 is een priemgetal

code:

Voer een getal in:
4294967297

1 is een priemgetal

Hij begint dus weer overnieuw.
Is het mogelijk dat ik verder kan gaan dan 4294967295?

[ Voor 0% gewijzigd door Xof op 15-10-2002 14:54 . Reden: ff wat enters ingedaan :) ]

[Soultaker]

Om te beginnen long long's gebruiken. (Of met Visual Studio __int64's), dan kun je nog 32 bits verder (en 18446744073709551615 is een best wel groot getal).

Waarschijnlijk kun je daarvan al niet meer fatsoenlijk berekenen of 't wel of niet priem is. Als dat wel het geval is, dan kun je overstappen op een big numeral library, maar de kans is groot dat dat VEEL trager werkt.

offtopic:
Je programma klopt niet; 0 en 1 zijn helemaal geen priemgetallen!

[Xof]

Ja nouja dat zijn uitzonderingen... buggy
Maar de rest klopt nml wel

long long, kan dat ook nog?

[Eskimootje]

Soultaker schreef op 15 oktober 2002 @ 14:55:
Om te beginnen long long's gebruiken. (Of met Visual Studio __int64's), dan kun je nog 32 bits verder (en 18446744073709551615 is een best wel groot getal).

Waarschijnlijk kun je daarvan al niet meer fatsoenlijk berekenen of 't wel of niet priem is. Als dat wel het geval is, dan kun je overstappen op een big numeral library, maar de kans is groot dat dat VEEL trager werkt.

offtopic:
Je programma klopt niet; 0 en 1 zijn helemaal geen priemgetallen!

offtopic:
1 kun je door zichzelf en door 1 ennix anders dus dat is wel een priemgetal. 0 is altijd bijzonder dus daarvan zou ik het niet weten.

[Soultaker]

Eskimootje schreef op 15 oktober 2002 @ 15:00:
1 kun je door zichzelf en door 1 ennix anders dus dat is wel een priemgetal. 0 is altijd bijzonder dus daarvan zou ik het niet weten.

Per definitie is 2 het eerste priemgetal, dus dat verhaal gaat niet op.

[SimplyMe]

Misschien ff stoeien met twee keer een unsigned long

kan je tot 18446744065119617025

das misschien wel mogelijk

[Xof]

code:

Voer een getal in:
4294967296

Deelbaar door:
2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
1073741824, 2147483648

4294967296 is geen priemgetal

code:

Voer een getal in:
4294967297

Deelbaar door:
641, 6700417

4294967297 is geen priemgetal

Zo long long werkt iig
Ga ik nu daarvan het grootste getal is berekenen... hoe lang zal die daar wel niet mee bezig zijn

[Eskimootje]

Mersenne RingNieuw wereld-record priemgetal ontdekt: M39!! ... Elk natuurlijk getal
behalve 1 is ofwel priemgetal, ofwel het product van priemgetallen. ...

die wiskundigen met hun uitzonderingen altijd.

[Verwijderd]

Eskimootje schreef op 15 oktober 2002 @ 15:00:

offtopic:
1 kun je door zichzelf en door 1 ennix anders dus dat is wel een priemgetal. 0 is altijd bijzonder dus daarvan zou ik het niet weten.

offtopic:
0 kun je door elk getal delen en dus is het geen priemgetal...en als 1 een priemgetal zou zijn, dan zou verder niets meer een priemgetal zijn, want alles is deelbaar door 1...

[.oisyn]

Eskimootje schreef op 15 oktober 2002 @ 15:00:
[...]

offtopic:
1 kun je door zichzelf en door 1 ennix anders dus dat is wel een priemgetal. 0 is altijd bijzonder dus daarvan zou ik het niet weten.

een priemgetal is een getal dat precies 2 delers heeft (in N). 1 heeft maar 1 deler, en is derhalve geen priem

[Eskimootje]

Jaaah nu weet ik het wel hoor, als jullie nou eens reageren voordat ik het opgezocht heb en neit allemaal hetzelfde

[Verwijderd]

2 is in mijn overtuiging ook geen priem getal . .ja het is alleen deelbaar door 1 en zichzelf. . maar er zijn ook geen andere mogelijkheden . ..

daarom heeft 2 dus ook de mogelijkheid niet om een NIET-PRIEM te zijn

[.oisyn]

Verwijderd schreef op 15 oktober 2002 @ 15:14:
2 is in mijn overtuiging ook geen priem getal . .ja het is alleen deelbaar door 1 en zichzelf. . maar er zijn ook geen andere mogelijkheden . ..

daarom heeft 2 dus ook de mogelijkheid niet om een NIET-PRIEM te zijn

onzin natuurlijk
want waarom zou je niet kunnen proberen of 2 deelbaar is door 3? Dus er zijn wel meer mogelijkheden

[Glimi]

.oisyn schreef op 15 oktober 2002 @ 15:11:
een priemgetal is een getal dat precies 2 delers heeft (in N). 1 heeft maar 1 deler, en is derhalve geen priem

N wordt door veel mensen anders gedefinieerd.
Je bedoel hiermee alle positieve natuurlijke getallen vanaf 1

[Xof]

Alleen kan ik die uitzondering er niet inkrijgen...

if ( i == 0 || i == 1 )
enz enz.

Dan blijft die hangen

[Soultaker]

Eskimootje schreef op 15 oktober 2002 @ 15:13:
Jaaah nu weet ik het wel hoor, als jullie nou eens reageren voordat ik het opgezocht heb en neit allemaal hetzelfde

Als jij nou eens reageert nadat je het opgezocht hebt, hoeven we je niet te verbeteren. Daarbij geeft iedereen een andere goede definitie, dus dat is niet allemaal hetzelfde.

[.oisyn]

nog even alles bij elkaar, voor the sake of argument

A prime number (or prime integer, often simply called a "prime" for short) is a positive integer p > 1 that has no positive integer divisors other than 1 and p itself. (More concisely, a prime number p is a positive integer having exactly one positive divisor other than 1.) For example, the only divisors of 13 are 1 and 13, making 13 a prime number, while the number 24 has divisors 1, 2, 3, 4, 6, 8, 12, and 24 (corresponding to the factorization ), making 24 not a prime number. Positive integers other than 1 which are not prime are called composite numbers. The number 1 is a special case which is considered neither prime nor composite (Wells 1986, p. 31).


Although the number 1 used to be considered a prime (Lehmer 1909; Lehmer 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp. 86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46), it requires special treatment in so many definitions and applications involving primes greater than or equal to 2 that it is usually placed into a class of its own. As noted by Tietze (1965, p. 2), "Why is the number 1 made an exception? This is a problem that schoolboys often argue about, but since it is a question of definition, it is not arguable." The smallest prime is therefore 2. However, since 2 is the only even prime, it is also somewhat special, the set of all primes excluding 2 is called the "odd primes." Note also that while 2 is considered a prime today, at one time it was not (Tietze 1965, p. 18; Tropfke 1921, p. 96). Excluding 1 and including 2, the first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (Sloane's A000040; Hardy and Wright 1979, p. 3), and the set of primes is sometimes denoted . The th prime for n = 0, 1, ... is given by 2, 29, 541, 7919, 104729, 1299709, 15485863, 179424673, 2038074743, ... (Sloane's A006988; Graham et al. 1990, p. 111).

bron: http://mathworld.wolfram.com/PrimeNumber.html

.edit: wil ik trouwens nog even reageren op deze quote van Tietze:

However, since 2 is the only even prime, it is also somewhat special, the set of all primes excluding 2 is called the "odd primes."

dat is natuurlijk gewoonweg bullshit. Er staat dat 2 de enige priem is dat deelbaar is door 2. Ja duh!, 3 is de enige priem die deelbaar is door 3, en 5 door 5. Nogal logisch

[zoepercavia]

dat is natuurlijk gewoonweg bullshit. Er staat dat 2 de enige priem is dat deelbaar is door 2. Ja duh!, 3 is de enige priem die deelbaar is door 3, en 5 door 5. Nogal logisch

nee, alle priemgetallen behalve 2 hebben behalve dat ze priemgetallen zijn ook nog met elkaarovereen dat ze oneven zijn. Zij hebben dus meer met elkaar gemeen, daarom zou je 2 als speciaal kunnen zien.
Maar 2 moet er iig wel bij.

[Reptile209]

Xof schreef op 15 oktober 2002 @ 15:27:
Alleen kan ik die uitzondering er niet inkrijgen...

if ( i == 0 || i == 1 )
enz enz.

Dan blijft die hangen

if (i < 2) == korter

Hoezo "blijft hangen"? (Weet even niet meer hoe de volgorde in C++ zit, maar evalueert dit niet tot i == ( 0 || i ) == 1 ? En moet je dan dus niet (i==0) || (i==1) doen? Of mijn < 2 versie?)

[Eskimootje]

Soultaker schreef op 15 oktober 2002 @ 16:35:
[...]

Als jij nou eens reageert nadat je het opgezocht hebt, hoeven we je niet te verbeteren. Daarbij geeft iedereen een andere goede definitie, dus dat is niet allemaal hetzelfde.

* Eskimootje was er van overtuigd dat 1 ook een priemgetal was. (ik had nl. geleerd dat alles wat alleen deelbaar door zichzelf of deelbaar door een was een priemgetal is.

[.oisyn]

zoepercavia schreef op 15 oktober 2002 @ 18:34:
[...]


nee, alle priemgetallen behalve 2 hebben behalve dat ze priemgetallen zijn ook nog met elkaarovereen dat ze oneven zijn. Zij hebben dus meer met elkaar gemeen, daarom zou je 2 als speciaal kunnen zien.
Maar 2 moet er iig wel bij.

wat is een even getal? een getal dat door 2 deelbaar is

en alle priemgetallen behalve 3 hebben met elkaar overeen dat ze niet door 3 deelbaar zijn
en alle priemgetallen behalve 5 hebben met elkaar overeen dat ze niet door 5 deelbaar zijn

dus wat is er dan zo speciaal aan 2?

[windancer]

Gaat het nog steeds op :

alle priemgetallen behalve 3 hebben met elkaar gemeen dat ze geen drievoud zijn. Daardoor vind ik 3 speciaal.

Of lekker generiek : alle priemgetallen behalve N hebben met elkaar gemeen dat ze geen N-voud zijn. Daarom is N speciaal.

zoepercavia schreef op 15 oktober 2002 @ 18:34:
[...]

nee, alle priemgetallen behalve 2 hebben behalve dat ze priemgetallen zijn ook nog met elkaarovereen dat ze oneven zijn. Zij hebben dus meer met elkaar gemeen, daarom zou je 2 als speciaal kunnen zien.
Maar 2 moet er iig wel bij.

[toraq]

.oisyn schreef op 15 oktober 2002 @ 18:54:

[...]


wat is een even getal? een getal dat door 2 deelbaar is

en alle priemgetallen behalve 3 hebben met elkaar overeen dat ze niet door 3 deelbaar zijn
en alle priemgetallen behalve 5 hebben met elkaar overeen dat ze niet door 5 deelbaar zijn

dus wat is er dan zo speciaal aan 2?

Dat je aan de hand van delen door 2 kan zeggen of iets even of oneven is, terwijl er niet zulke woorden voor de andere priemgetallen bestaan

[windancer]

Als 1 een priemgetal was dan had je geen unieke factorisatie van de natuurlijke getallen in priemfactoren. Immers, 2.2.3 en 1.2.2.3 zouden dan beide priemfactorisaties zijn van het getal 12.

[Fairy]

Was dat niet het principe van OGR

[Verwijderd]

Om ff op de vraag terug te komen:

Je kunt ook n soort BigInteger klasse maken (die zit in java).
Deze maakt gebruik van arrays om het getal in op te slaan (elk cijfer 1 array 'vakje').

Zo kun je HELE grote getallen maken.

Suc6

[.oisyn]

Fairy schreef op 15 oktober 2002 @ 19:16:
Was dat niet het principe van OGR

nee, priemgetallen hebben niets te maken met de Optimal Golomb Ruler

[kvdveer]

Verwijderd schreef op 15 oktober 2002 @ 19:21:
Om ff op de vraag terug te komen:

Je kunt ook n soort BigInteger klasse maken (die zit in java).
Deze maakt gebruik van arrays om het getal in op te slaan (elk cijfer 1 array 'vakje').

Ze gebruiken inderdaad 1 arrayelement per cijfer, maar het gaat dan niet om cijfers van 0 tot 10 (base10) maar om cijfers van 0 tot 2^32... Dat maakt bitwise bewerkingen eenvoudiger.
Onder andere modulo en vermenigvuldigen vereisen bitwise bewerkingen.... Je wilde toch niet herhaald gaan optellen mag ik hopen...

[Dr Nix]

Ik neem aan dat jouw programma'tje het ingevoerde getal gaat delen door alle oneven getallen groter dan 1? Tot hoever ga je dan?

Ik heb namelijk ook een keer zo'n programma gemaakt, (waarmee alle priemgetallen vanaf 2 werden gevonden, hoe langer ik hem liet rekenen, hoe meer ik er vond), voor mijn grafische rekenmachine.
Aangezien zijn rekenkracht niet zo groot is, moest alles zo efficient mogelijk. Toen heb ik bedacht dat je dus alleen door oneven getallen hoeft te delen, en niet verder hoeft te gaan dat de wortel van het te onderzoeken getal !!
Misschien heb je dit zelf ook al bedacht, maar ik vond mezelf toen heel slim

[kvdveer]

B2000.5 schreef op 16 oktober 2002 @ 00:01:
Ik neem aan dat jouw programma'tje het ingevoerde getal gaat delen door alle oneven getallen groter dan 1? Tot hoever ga je dan?

Ik heb namelijk ook een keer zo'n programma gemaakt, (waarmee alle priemgetallen vanaf 2 werden gevonden, hoe langer ik hem liet rekenen, hoe meer ik er vond), voor mijn grafische rekenmachine.
Aangezien zijn rekenkracht niet zo groot is, moest alles zo efficient mogelijk. Toen heb ik bedacht dat je dus alleen door oneven getallen hoeft te delen, en niet verder hoeft te gaan dat de wortel van het te onderzoeken getal !!
Misschien heb je dit zelf ook al bedacht, maar ik vond mezelf toen heel slim

Ooit van de zeef van erostenes gehoord?

Gaat als volgt: Je hebt een grote set met getallen van 2 tot en met [x].
Je neemt het eerste getal er uit en voegt het toe aan de lijst met priemgetallen, en je verwijdert vervolgens alle veelvouden daarvan uit de lijst. Dit doe je tot je bulk-lijst leeg is. Je hebt dan alle priemgetallen gevonden kleiner dan [x]
Tot slot verwijder je nog even 2 uit de lijst met priemgetallen...

Omdat een veelvoud berekenen eenvoudiger is dan een deling gaat dit hoogstwaarschijnlijk sneller dan jou berekening.

[cameodski]

kvdveer schreef op 26 oktober 2002 @ 01:52:
Omdat een veelvoud berekenen eenvoudiger is dan een deling gaat dit hoogstwaarschijnlijk sneller dan jou berekening.

Maar worden hier ook niet een heleboel onnodige berekeningen gedaan? Als je bijvoorbeeld alle veelvouden van 2 verwijdert hebt en je gaat daarna verder met 3 en verwijdert daarvan alle veelvouden dan is de helft van de veelvouden al onnodig, omdat die bij 2 al verwijderd zijn.
Dan zou je natuurlijk alleen de 'oneven' veelvouden (3 x 3, 5 x 3, 7 x 3 enz) kunnen pakken, maar het wordt in ieder geval een stuk complexer om te implementeren.

[Soultaker]

Met de zeef van Eratosthenes doe je een heleboel operaties. Gelukkig hoef je 'doorgestreepte' getallen niet meer te beschouwen en is het aantal veelvouden van de hogere getallen vrij klein.

Ik heb hier geen vergelijkingsmateriaal, maar het lijkt me toch dat de zeef van Eratosthenes alleen een optie is als je alle priemgetallen kleiner dan X wilt hebben. Als je gewoon N priemgetallen wilt hebben, of wilt weten of een bepaald getal priem is, kun je beter gewoon uitzoeken of 'ie delers heeft.

Als je op zoek bent naar de eerste X priemgetallen, kan ik me voorstellen dat je je gevonden priemgetallen in een array stopt en nieuwe getallen daartegen controleert (complexiteit is O(N^2)). Het effect is hetzelfde als de zeef, met het verschil dat je geheugenruimte bespaart door niet alle getallen tot je hoogste priemgetal op te slaan, maar alleen de gevonden priemgetallen. Bij hoge priemgetallen (die schaarser zijn) kan dat aanzienlijk in geheugengebruik schelen.

[Soultaker]

Ik merk dat ik allemaal foute dingen zeg. Het schijnt dat de zeefmethode is te optimaliseren tot O(N * log(log(N)) ) - dat is natuurlijk een stuk beter dan wat ik voorstelde.

[Verwijderd]

Hier staat een linkje naar een pdf'je waarin een algoritme wordt beschreven, dat momenteel als snelste test of een getal priem is of niet, en nog geeneens zo moeilijk is .

_{Althans, zoveel begreep ik ervan}

[Soultaker]

Interessante link! Ook leuk om te zien dat je zulke (toch niet onbelangrijke) ontdekkingen in een document van 9 pagina's (inclusief referenties, acknowledgments en inleiding, e.d.) kwijtkunt.

[Lord Daemon]

Het is inderdaad zeer interessant om te zien dat het berekenen van priemgetallen inderdaad binnen polynomiale tijd kan gebeuren. Maar welk algoritme gebruikt de topicstarter?

(Jammer dat het vinden van priemgetallen geen NP-compleet probleem was, anders was die paper hierboven de belangrijkste wiskundige ontdekking van de eeuw geweest.)

[Verwijderd]

Even heel flauw hoor, maar als je niet per se de noodzaak voelt om alle delers van een getal te berekenen, zou je in je code op kunnen nemen dat wanneer het laatste cijfer van de integer gelijk is aan 0 of aan 5, je dit getal direkt als niet-priemgetal bestempelt.

_{Voor de trage hersentjes: 5 is een priemgetal, iedere integer eindigend op 0 of 5 is deelbaar door 5.}

edit:


Dit is dan toch zeker sneller bij grotere getallen

[Verwijderd]

Lord Daemon schreef op 26 oktober 2002 @ 11:42:
(Jammer dat het vinden van priemgetallen geen NP-compleet probleem was, anders was die paper hierboven de belangrijkste wiskundige ontdekking van de eeuw geweest.)

En dan waren die gasten nu 1 miljoen dollars rijker . Zie hier. Maar áls het NP-volledig was, dan was de kans op dit algoritme ook 0.0 % geweest...

Maar wat ik me nu afvraag: is dit algoritme sneller dan de al bestaand (probabilistische) versies, en zo ja, heeft dit invloed op de kwaliteit van encryptie waar toch vaak van priems gebruik wordt gemaakt.

[ Voor 0% gewijzigd door Verwijderd op 26-10-2002 12:04 . Reden: URL toegevoegd ]

[Lord Daemon]

Verwijderd schreef op 26 oktober 2002 @ 12:00:
Dit is dan toch zeker sneller bij grotere getallen

Aangezien het bekijken van het laatste cijfer niet veel minder tijd zal kosten dan bekijken of het deelbaar is door 5, lijkt het me niet dat je hier echt tijdswinst mee gaat boeken.

Verwijderd schreef op 26 oktober 2002 @ 12:03:
Maar áls het NP-volledig was, dan was de kans op dit algoritme ook 0.0 % geweest...

Hoe bedoel je? Het is niet bewezen dat NP ongelijk is aan P.

Maar wat ik me nu afvraag: is dit algoritme sneller dan de al bestaand (probabilistische) versies, en zo ja, heeft dit invloed op de kwaliteit van encryptie waar toch vaak van priems gebruik wordt gemaakt.

Ja, in ieder geval in de limiet voor n->infinity wel. Of het ook al sneller is voor de priemgetallen waar men bij encryptie mee werkt weet ik niet.

[Soultaker]

Verwijderd schreef op 26 oktober 2002 @ 12:00:
Even heel flauw hoor, maar als je niet per se de noodzaak voelt om alle delers van een getal te berekenen, zou je in je code op kunnen nemen dat wanneer het laatste cijfer van de integer gelijk is aan 0 of aan 5, je dit getal direkt als niet-priemgetal bestempelt.

En hoe bepaal je dat? Door te kijken of 't getal deelbaar is door 5. Puur op basis van statistiek is de kans echter groter dat je getal deelbaar is door 2 of 3, dus daar kun je beter eerst op controleren.

Je methode is dus niet zo heel slim. Het komt er gewoon op neer, dat je controleert of je getal deelbaar is door een priemgetal (zoniet, dan is het geen priemgetal). Het nut van controleren of een getal priem met 5 is, lijkt me miniem. Als je getallen zoekt die gegarandeerd niet priem zijn, kun je beter controleren of ze deelbaar zijn door 2.

[Verwijderd]

Soultaker schreef op 26 oktober 2002 @ 13:24:
[...]


En hoe bepaal je dat? Door te kijken of 't getal deelbaar is door 5. Puur op basis van statistiek is de kans echter groter dat je getal deelbaar is door 2 of 3, dus daar kun je beter eerst op controleren.

Je methode is dus niet zo heel slim. Het komt er gewoon op neer, dat je controleert of je getal deelbaar is door een priemgetal (zoniet, dan is het geen priemgetal). Het nut van controleren of een getal priem met 5 is, lijkt me miniem. Als je getallen zoekt die gegarandeerd niet priem zijn, kun je beter controleren of ze deelbaar zijn door 2.

hmm, ik had kunnen weten dat mijn kennis van efficiëntie niet toereikend was om uitspraken over dit soort dingen te doen maar ik was afgelopen week toevallig ook bezig met het schrijven van een algoritme, dus ik dacht laat ik het even vragen

[Verwijderd]

dus alle priemgetallen boven de 10 eindigen NIET op een 0, 2, 4, 5, 6, 8 dus je hoeft maar te kijken naar getallen die op 1,3,7,9 eindigen...

[Lord Daemon]

Verwijderd schreef op 26 oktober 2002 @ 19:24:
dus alle priemgetallen boven de 10 eindigen NIET op een 0, 2, 4, 5, 6, 8 dus je hoeft maar te kijken naar getallen die op 1,3,7,9 eindigen...

Het punt is dat kijken of een getal op een 4 eindigt niet minder werk is dan kijken of een getal deelbaar is door 2.

[vinnux]

Om te weten of een getal N een priemgetal is, moet de modulo (%) van N door alle voorgaande priemgetallen - kleiner of gelijk aan de wortel van N - groter dan 0 zijn.
Zo zou ik hem schrijven voor getallen kleiner dan 32 bit. Voor 64 bits getallen heb ik hem nog niet geprobeerd.

edit:

Zoals verwacht zijn 64 bits getallen te groot voor deze methode. Wist ik eigenlijk al voor dat ik het probeerde.

2 is geen speciale priem. Toevallig heeft de verzameling die N%2=0 heet de naam even en alles wat erbuiten valt oneven. Dat er van deze verzameling maar één een priemgetal is is te wijten aan de definitie van priemgetallen. Allesverzamelingen waarin N%Y gedaan word is N alleen een mogelijk priemgetal.

[Lord Daemon]

vgouw schreef op 26 oktober 2002 @ 20:44:
Om te weten of een getal N een priemgetal is, moet de modulo (%) van N door alle voorgaande priemgetallen - kleiner of gelijk aan de wortel van N - groter dan 0 zijn.

Nee, dat is dus niet het geval. Dit algoritme is immers niet in staat om priemgetallen binnen polynomiale tijd te vinden: het zal exponentieel langer duren om priemgetallen te vinden als de getallen groter worden. Hierboven staat een linkje naar een artikel waarin een beter algoritme wordt beschreven.

[.oisyn]

Lord Daemon schreef op 26 oktober 2002 @ 20:42:
[nohtml]
[...]
[/nohtml]Het punt is dat kijken of een getal op een 4 eindigt niet minder werk is dan kijken of een getal deelbaar is door 2.

sterker nog, een and instructie is slechts 1 cycle, terwijl de div instructie kan oplopen tot wel 20 cycles... testen op even of oneven is dus een stuk sneller dan testen of een getal eindigt op 4 (ruime schatting gebaseerd op een pentium, kan dus wel verschillen met de werkelijkheid (de cpu's van tegenwoordig), maar het blijft een factor langzamer)

[vinnux]

En heeft iemand al een implementatie van dat geweldige document?

Vind ik wel iets voor ACM toch
http://www.claymath.org/prizeproblems/pvsnp.htm

[DroogKloot]

KoenM schreef:
[...]

Maar wat ik me nu afvraag: is dit algoritme sneller dan de al bestaand (probabilistische) versies, en zo ja, heeft dit invloed op de kwaliteit van encryptie waar toch vaak van priems gebruik wordt gemaakt.

Nee, het is voor grote n zeker niet sneller. Sterker nog, er valt van alles aan te optimaliseren.

De invloed op encryptietechnieken is trouwens positief, omdat dit algoritme het vinden van priemgetallen --of, beter gezegd, het vaststellen van primaliteit-- een stuk eenvoudiger (want non-probabilistisch) maakt.

[Lord Daemon]

DroogKloot schreef op 27 oktober 2002 @ 20:04:
Nee, het is voor grote n zeker niet sneller. Sterker nog, er valt van alles aan te optimaliseren.

Het is niet sneller? Waarom zou het niet sneller zijn?

[Confusion]

toraq schreef:
Dat je aan de hand van delen door 2 kan zeggen of iets even of oneven is, terwijl er niet zulke woorden voor de andere priemgetallen bestaan

Dat is erg onzorgvuldig uitgedrukt. Elk getal is deelbaar door twee. Een even getal is een getal dat modulo twee nul oplevert. Dus is 2 het enige even priemgetal. Of ligt in de definitie van priemgetal ook vast dat het tot de set van natuurlijke getallen moet behoren of iets dergelijks?

[.oisyn]

[nohtml]

Fused schreef op 28 oktober 2002 @ 00:03:
[...]

Dat is erg onzorgvuldig uitgedrukt. Elk getal is deelbaar door twee.

een getal is deelbaar door x als een deling door x een getal in Z oplevert
5 is dus niet deelbaar door 2, want 2.5 komt niet in Z voor (maar in Q)

Dat is de wiskundige definitie

[PiepPiep]

Als je niet perse de factoren wilt hebben kan je ook kijken of het waarschijnlijk priem is.
Dit doe je met 2^(p-1) mod p
Als er 1 uit komt is het waarschijnlijk priem, als er iets anders uit komt is het geen priem.
Hierna kan je 3^(p-1) mod p doen, weer hetzelfde, 1 waarschijnlijk priem, iets anders geen priem.
Als je wilt kan je de 2 en 3 vervolgens vervangen voor 5, 7, 11, 13, 17, 19 enz...
Ik geloof dat de kans op dat er 1 uit komt als het geen priem is iets van 0.01% is ofzo.

voorbeeld:
p = 7
2^(p-1) mod p = 2^(7-1) mod 7 = 64 mod 7 = 1 -> waarschijnlijk priem
3^(p-1) mod p = 3^(7-1) mod 7 = 729 mod 7 = 1 -> waarschijnlijk priem voor 99.99% zeker ofzo.

p = 15
2^(p-1) mod p = 2^(15-1) mod 15 = 16384 mod 15 = 4 -> zeker geen priem!

Met zeer grote getallen is dit ook goed uit te rekenen,

(zomaar voorbeeld, geen priem)
12345^67890 mod 23456 = (12345*12345) ^ (67890/2) mod 23456
nu kan je 12345*12345 alvast uitrekenen en alvast mod 23456 doen.
Als het getal op de plaats van 67890 oneven is, kan je 67890/2 afronden naar beneden en moet je ff onthouden dat het dus (12345*12345) ^ (67891/2) mod 23456 * 12345 wordt.
Als het hierna bv 345*345 wordt met een oneven exponent krijg je dus die 12345 * 345 die je vervolgens ook kan uitrekenen en alvast mod 23456 kan doen.

Ik hoop dat het een beetje duidelijk is ;P maar ik moet nu naar werk, misschien tik ik vanmiddag nog wel een soort pseudo code in die wel wat duidelijker zal zijn.

[Confusion]

.oisyn schreef:
een getal is deelbaar door x als een deling door x een getal in Z oplevert
5 is dus niet deelbaar door 2, want 2.5 komt niet in Z voor (maar in Q)

Dat is de wiskundige definitie

Stiekem is het ook taalkundig geneuzel. Je moet in taal iets niet onzorgvuldiger gaan uitdrukken dan nodig. 'Deelbaar zijn door' is gewoon onnauwkeurig, ongeacht hoe je het herdefinieert (taal heeft tenslotte al een betekenis; je kan niet zomaar een kreet gaan herdefinieren, dat schept verwarring); je kan beter spreken over 'een integer veelvoud zijn van' of iets dergelijks.

[Lord Daemon]

PiepPiep schreef op 28 oktober 2002 @ 08:23:
Als je niet perse de factoren wilt hebben kan je ook kijken of het waarschijnlijk priem is.
Dit doe je met 2^(p-1) mod p
Als er 1 uit komt is het waarschijnlijk priem, als er iets anders uit komt is het geen priem.

Er geldt inderdaad de 'kleine stelling van Fermat':

Kleine stelling van Fermat:
Zij p priem, a geen veelvoud van p, dan
a^(p-1) = 1 mod p

Echter, dit is geen voldoende voorwaarde, dus zal je alsnog moeten gaan checken of het inderdaad een priemgetal is. Ik weet niet zeker hoeveel je er mee opschiet, omdat machtsverheffen naar p-1 voor grote p me een erg rekenintensieve operatie lijkt.

[Janoz]

Lord Daemon schreef op 28 oktober 2002 @ 10:02:
[nohtml]
[...]
[/nohtml]Er geldt inderdaad de 'kleine stelling van Fermat':


[...]
Echter, dit is geen voldoende voorwaarde, dus zal je alsnog moeten gaan checken of het inderdaad een priemgetal is. Ik weet niet zeker hoeveel je er mee opschiet, omdat machtsverheffen naar p-1 voor grote p me een erg rekenintensieve operatie lijkt.

Gelukkig hebben ze voor a^bmod c een efficient algo bedacht waardoor je het tussen resultaat niet meer nodig hebt ..


Verder wil ik nog ff terugkomen op de mensen die een getal willen controleren op de laatste digit(s). Besef dat een getal in het geheugen niet in base10 opgeslagen is. Voor de mens is het mischien wel makkelijker te zien dat een getal eindigd op 5, maar waneer dit in base2 opgeslagen is, is dit alweer een stuk lasitger. Voor de computer is het veel makkelijker om met veelvouden van 2 te werken. Toch zullen deze optimalisaties weinig invloed hebben op de werkelijke lengte van je algoritme. Eigenlijk ben je nu gewoon bezig om hardgecodeerd in je programma alsnog de eerder genoemde zeef te implementeren.

[.oisyn]

Fused schreef op 28 oktober 2002 @ 09:53:
[...]

Stiekem is het ook taalkundig geneuzel. Je moet in taal iets niet onzorgvuldiger gaan uitdrukken dan nodig. 'Deelbaar zijn door' is gewoon onnauwkeurig, ongeacht hoe je het herdefinieert (taal heeft tenslotte al een betekenis; je kan niet zomaar een kreet gaan herdefinieren, dat schept verwarring); je kan beter spreken over 'een integer veelvoud zijn van' of iets dergelijks.

Das natuurlijk 1 grote duh en daarom gewoon sex met mieren, en hier ook totaal niet aan de orde. Dit is een wiskundig topic, dus we bedoelen het gewoon zoals je wiskunde docent het ook zou bedoelen

[PommeFritz]

Om terug te komen naar te topicstarter, hoe om te gaan met getallen groter dan een long: kijk eens naar de GNU MP library (http://www.swox.com/gmp/) als je met C/C++ bezig bent. Anders naar BigInteger als je in Java bezig bent.
In de GNU MP library zitten wat getaltheoretische functies die heel snel met een bepaalde zekerheid kunnen bepalen of een (groot!) getal priem is, zie b.v.
hier.

[Verwijderd]

toraq schreef op 15 oktober 2002 @ 19:12:
[...]


Dat je aan de hand van delen door 2 kan zeggen of iets even of oneven is, terwijl er niet zulke woorden voor de andere priemgetallen bestaan

Dit wou ik net posten , hier ben ik het mee eens

[Soultaker]

Verwijderd schreef op 28 oktober 2002 @ 23:30:
Dit wou ik net posten , hier ben ik het mee eens

Daar ben je dan knap laaat mee - dat bericht is twee weken oud!

Compleet

offtopic:
Waarom staat er boven de topics "Door Soultaker - Tuesday 29 October 2002 00:07" maar in de quote "klaze schreef op 28 oktober 2002 @ 23:30"? (Ik heb het natuurlijk over de formattering van de datum).

[Lord Daemon]

[nohtml]

Janoz schreef op 28 oktober 2002 @ 11:08:
Gelukkig hebben ze voor a^bmod c een efficient algo bedacht waardoor je het tussen resultaat niet meer nodig hebt ..

Tja, dat zou kunnen. Neemt niet weg dat het wel een noodzakelijke maar geen voldoende voorwaarde is voor het zijn van een priemgetal, zodat je alsnog altijd op conventionele wijze zal moeten checken of een bepaald 'kansrijk' getal inderdaad priem is.

[Belgar]

Snelste implementatie die ik heb geschreven saved elk priemgetal naar een file (array kan ook). Vervolgens wordt elk nieuw getal gedeeld door elk getal in het array. zit er geen enkele modulo '0' bij is het een priemgetal. Een en ander is natuurlijk wel geoptimaliseerd. array wordt doorgewerkt tot wortel van het onderzochte getal, en alleen oneven getallen worden beschouwd. Voor de hogere getallen is dit een factor 6-20 sneller dan 'deel maar raak voor een knaak'. Heb ik een keer moeten schrijven voor school. grote voordeel is dat je altijd maar 1 keer hoeft te zoeken. Is je array eenmaal weggeschreven kan je die altijd weer binnenhalen.

[Verwijderd]

Belgar>> 10 tegen 1 dat een zeefalgoritme sneller priemen genereert dan jij ze van disk kunt lezen. Daarom vind je ook nergens "primefiles", het is gewoon sneller priemen on-the-fly te genereren.

[Lord Daemon]

Verwijderd schreef op 29 oktober 2002 @ 15:00:
Daarom vind je ook nergens "primefiles", het is gewoon sneller priemen on-the-fly te genereren.

Nergens? ftp://ftp.mirror.ac.uk/si...nberg/etext93/prime12.txt

[.oisyn]

Lord Daemon schreef op 29 oktober 2002 @ 17:51:
[nohtml]
[...]
[/nohtml]Nergens? ftp://ftp.mirror.ac.uk/si...nberg/etext93/prime12.txt

het genereren van de eerste 100.000 priemgetallen gaat bij mij sneller dan het downloaden van die textfile (adsl @ 512 kbps, athlon xp @ 1400 mhz)

[Lord Daemon]

Niet als je eerst nog C moet opstarten om de code te compileren.

[.oisyn]

C opstarten? grappig

[Verwijderd]

Schiet me net te binnen:
[rml][ Java] Priemgetallen genereren[/rml]
Daar heb ik een zeef gepost die de eerste 100.000 priemen in ongeveer een halve seconde uitrekent (in java). Om precies te zijn 630ms op een Athlon@1200. Er zijn nog meer optimalisaties denkbaar aan het algoritme dat ik post, maar die gaan pas echt meetellen als je in de buurt van de 100.000.000 priemen gaat genereren, bij 100.000 priemetjes vertraagt het alleen maar.

edit:
Correctie: dit algoritme zoekt alle priemen onder de 100.000 op deze manier, maar het gaat om het idee van de snelheid van de zeef.

[Verwijderd]

zoepercavia schreef op 15 oktober 2002 @ 18:34:
[...]


nee, alle priemgetallen behalve 2 hebben behalve dat ze priemgetallen zijn ook nog met elkaarovereen dat ze oneven zijn. Zij hebben dus meer met elkaar gemeen, daarom zou je 2 als speciaal kunnen zien.
Maar 2 moet er iig wel bij.

Alle priemgetallen behalve 2 en 3 hebben met elkaar gemeen dat ze:
- Oneven zijn
- Niet deelbaar door 3 zijn!

Dus moeten we 3 ook maar als een speciaal priemgetal opvatten?

[RickN]

Ik geloof dat nog niet gemeld is dat elk priem getal groter dan 3 geschreven kan worden als:
6x+1 of 6x-1.
Oftewel, elk priemgetal groter dan 3 is een 6-voud, plus of min 1.

code:

1    2    3    4    5    6
7    8    9    10   11   12
13   14   15   16   17   18
enz...

je kunt de colommen die beginnen met 2,3,4 en 6 weggooien.

Wat overblijft is te schrijven als 6x+1 of 6x-1

Ik heb eerder ooit deelgenomen aan deze discussie op Anandtech, misschien dat je er iets aan hebt: klik

[.oisyn]

RickN: das idd een vrij logische redenering. Wat je nu doet is simpelweg alle getallen die deelbaar zijn door 2 en 3 elimineren.

Dat is een herhalende reeks: het begin (bij 0) is deelbaar door 2 en 3. Daarna komt een getal dat door geen van beide deelbaar is, dan een door 2, dan een door 3, dan een door 2, dan weer geen van beide. De lengte van deze reeks is 2 * 3 = 6 getallen. (Het volgende getal zou dus weer deelbaar zijn door 2 en 3, net als bij 0)

Hier kun je 5 ook bij betrekken, je krijgt dan een reeks van 30 lang (2 * 3 * 5)
En dus zijn alle priemen die groter zijn dan 15 te schrijven als:
30x - 1 of 30x + 1 of
30x - 7 of 30x + 7 of
30x - 11 of 30x + 11 of
30x - 13 of 30x + 13

Op zich zou je nog kunnen testen of een priem te schrijven is als een van deze getallen, en zo niet: iig geen priem. Maar simpelweg testen of ze deelbaar zijn door 2, 3 of 5 gaat sneller

Waar je het wel voor zou kunnen gebruiken is voor de trial division, namelijk het vinden van mogelijke delers. Als je begint bij 3 en je telt er steeds 2 bij op, tot de wortel van het getal, dan elimineer je slechts alleen delers die veelvouden zijn van 2. Je kunt de 3 erbij nemen door gebruik te maken van bovenstaande reeks

Je doet 2 en 3 handmatig (zoals je 2 ook altijd al handmatig deed), en dan begin je bij 5. De volgende deler is 2 verder, 7 dus, en die daarna 4 verder. Zo wissel je steeds tussen +2 en +4, en elimineer je ook alle veelvouden van 3

De 5 kun je er ook nog bij nemen. Je test 2, 3 en 5 met de hand, en je begint bij 7. Vervolgens pas je deze reeks toe: +4, +2, +4, +2, +4, +6, +2, +6

Zo'n reeks is makkelijk te genereren voor de eerste x priemgetallen, waardoor je al behoorlijk wat delers die je toch niet nodig hebt (veelvouden van de eerste x priemgetallen) elimineert. Dit idee heb ik overigens ook wel eens geopperd in dat RSA getal factorizatie topic, maar volgens mij begrepen er niet veel mijn uitleg

ik zal m eens opzoeken

.edit: ah: [rml].oisyn in "[ All language] Programmeer webstrijd"[/rml]

[RickN]

Tja, in die discussie waar ik naar linkte was er iemand die dacht handig gebruik te kunnen maken van die 6-voud +/- 1 observatie, maar z'n verhaal is zo ingewikkeld en ad hoc dat ik al snel de interesse verloor . Overigens, uit die zelfde thread:

Anyway, I think I have worked out how to do it. It turns out that the gcd function is roughly linear with respect to the smaller of the two inputs so what I have done is to keep the product of all the past primes in the memory and then just tested if the gcd of the product of all the primes and the test number was 1. If this was so, it was a prime.

Dat is ook een leuke manier om priems te genereren, maar het lost niet het probleem van de topicstarter op....

[Confusion]

Goed, even verder vanuit een andere draad. Het betreft het snelste stuk code in die draad om priemgetallen te genereren en ik neem waar dat de tijd om alle priemgetallen tot 10⁷ of 10⁸ meer dan een factor 10 toeneemt, terwijl je minder dan een factor 10 extra rekenoperaties verwacht.

Fused schreef

Qua aantallen is dit waarschijnlijk, omdat de priemdichtheid steeds kleiner wordt, maar waarom gaat hij er meer dan een factor 10 langer over doen om minder dan een factor 3 (wegens wegstrepen 2, 3, 5, 7, etc.) etcetera getallen te checken, waarvan er ook nog relatief veel meer worden weggestreept (waarbij dat wegstrepen dan natuurlijk wel weer een factor tien meer tijd kost)?

Bij 10⁷ zouden er toch nog geen schijfoperaties moeten zijn (althans, een array of boolean lijkt me toch in 16 + 4 byte *10⁷ is ongeveer 40 MB moeten kunnen en ik mag hopen dat ik dat vrij heb (KDE2, mozilla, emacs, newsreader).

Mietje schreef

CPU caching is verantwoordelijk voor de snelheid, of het ontbreken daarvan. Een groot deel van de boolean array moet telkens weer doorlopen worden om composieten weg te strepen, en als die array veel groter is dan de cache vinden er dus veel trage geheugenoperaties plaats.

Fused schreef

Maar van 10⁷ naar 10⁸ neemt het aantal trage geheugenoperaties vrijwel lineair toe zou ik denken (cache grootte is dan véél kleiner dan arraygrootte). Waarom neemt de tijd dan toch niet lineair toe?

[RickN]

Fused schreef op 30 oktober 2002 @ 22:57:
Goed, even verder vanuit een andere draad. Het betreft het snelste stuk code in die draad om priemgetallen te genereren en ik neem waar dat de tijd om alle priemgetallen tot 10⁷ of 10⁸ meer dan een factor 10 toeneemt, terwijl je minder dan een factor 10 extra rekenoperaties verwacht.

Fused schreef

[...]


Mietje schreef

[...]


Fused schreef

[...]

Waar wil je naartoe, zonder meer informatie over het algoritme dat je aanhaalt zou ik niet weten wat ik hierop moet zeggen. Behalve dan dat als het algoritme een (geoptimaliseerde) implementatie van de Erasbladiebla zeef is je observaties wel overeen komen met hetgeen te verwachten is, omdat zoals reeds gezegd de asymptotische rekentijd n log log n is....

[.oisyn]

RickN: hij doelt op de laatste paar reacties van deze thread: [rml][ Java] Priemgetallen genereren[/rml], die nu op slot zit omdat het hetzelfde onderwerp is maar omhoog was gekicked door iemand

[RickN]

Ja, ik had dat draadje inmiddels ook gevonden.

Anyway, Fused, kijk maar naar de code, een loop binnen een loop, da's al nooit meer lineair. Het algoritme doorloop ontzettend vaak, een steeds kleiner deel van het array, met steeds groter wordende stappen, dit resulteerd erin dat er O(N^2)??? keer een array locatie wordt bezocht, of er bij dat bezoeken daadwerkelijk een waarde wordt geschreven doet er niet meer toe, dat is slecht een optimalisatie die niets aan de asymptotische rekentijd veranderd. Het wegstrepen waar je over spreekt is ook een beetje misleidend; wegstrepen doe je alleen zodat je achteraf weet wat wel en wat geen priemgetallen zijn. Een weggestreepte locatie wordt daarna nog vaak bezocht, zo zal de 15e locatie bezocht worden bij het wegstrepen van 3vouden en 5vouden, dat er bij het wegstrepen van 5vouden niet meer naar de locatie geschreven wordt is zoals gezegd maar een optimalisatie. Als je er op één of andere manier voor zou kunnen zorgen dat eenmaal weggestreepte locaties bij het wegstrepen van hogere veelvouden ECHT niet meer worden bezocht, dan zou je een asymptotische snelheids winst boeken, maar dat lukt je denk ik niet.

Ik denk eigenlijk niet eens dat het algoritme uit die andere thread die ideale rekentijd van n log log n heeft, ik denk eigenlijk eerder n log n of misschien zelfs n^2.

[Verwijderd]

RickN schreef op 31 oktober 2002 @ 00:24:
Anyway, Fused, kijk maar naar de code, een loop binnen een loop, da's al nooit meer lineair. Het algoritme doorloop ontzettend vaak, een steeds kleiner deel van het array, met steeds groter wordende stappen, dit resulteerd erin dat er O(N^2)??? keer een array locatie wordt bezocht

De complexiteit van deze zeef is lastig te beschrijven. Ten eerste loopt de buitenste loop maar tot sqrt(N), en de stapgroote in de binnenste loop neemt linear toe. Ik heb geen zin om er verder moeilijk over te gaan doen

[ Voor 0% gewijzigd door Verwijderd op 31-10-2002 02:50 . Reden: ik schreef iets doms, tis laat :) ]

[kvdveer]

Verwijderd schreef op 31 oktober 2002 @ 02:33:
[...]

De complexiteit van deze zeef is lastig te beschrijven. Ten eerste loopt de buitenste loop maar tot sqrt(N), en de stapgroote in de binnenste loop neemt linear toe. Ik heb geen zin om er verder moeilijk over te gaan doen

Het is zelfs nog ingewikkelder dan dat...
Suppose de volgende pseudocode:

code:

int volgendeprime;
int counter =0;
int counter_in = 0;
bool[n] primes = true[n];

while(counter < ceil(sqrt(n))) {
  if(!bool[counter]) break;
  print "N is een prime";
  for(i=n;i<n;i+=counter) {
    bool[counter]=false;
  }
}
while(counter < n) {
  if(!bool[counter]) break;
  print "N is een prime";
}

In die eerste loop halen we alle priemgetallen kleiner dan wortel n... Alle getallen die groter zijn dan dat die daarna nog over zijn, zijn gegarandeerd ook priemgetallen.
Die eerste loop loopt niet sqrt(n) maal, kijk maar naar de eerste statement er in, die breakt als het betreffende getal geen prime is. In praktijk loop dat loopje dus: het aantal priemgetallen kleiner dan sqrt(n). hier lezen we dat dat aantal gelijk is aan n/ln(n) (bij benadering).
Dat interne loopje loopt n/counter maal. Dat loopt dus omgekeerd evenredig terug, naar mate het algo vordert. De complexiteitsfactor is hier echter gewoon n (dit weet ik niet zeker)

Het tweede loopje heeft een complexiteit van iets minder dan n: (n-sqrt(n)) Die complexiteit is minder dan het bovenstaande algo, dus wordt bij de O notatie genegeerd.

De complexiteit voor het bovenstaande algo is dus: O((n²)/_{ln (n)})

[ Voor 0% gewijzigd door kvdveer op 31-10-2002 11:00 . Reden: foutje... ]

[Confusion]

RickN schreef:
Het wegstrepen waar je over spreekt is ook een beetje misleidend; wegstrepen doe je alleen zodat je achteraf weet wat wel en wat geen priemgetallen zijn. Een weggestreepte locatie wordt daarna nog vaak bezocht, zo zal de 15e locatie bezocht worden bij het wegstrepen van 3vouden en 5vouden, dat er bij het wegstrepen van 5vouden niet meer naar de locatie geschreven wordt is zoals gezegd maar een optimalisatie.

Ach, inderdaad.

Op de een of andere manier is het wel mogelijk een O( log(n)¹² ) te krijgen, dus volgens mij moet het wel kunnen om te zorgen dat locaties niet herbezocht worden. Dat, of er is een heel andere aanpak vereist.