Priemgetallen, in het bijzonder Mersenne-priemen

[link0007]

Beste wiskundige onder ons,

Ik ben sinds het nieuws over de 44ste mersenne priem "gefascineerd" over wiskundig programmeren. Het enige wat mij zwaar in de weg ligt is dat ik pas op 4HAVO zit, en dus nog geen bal over belangrijke dingen heb geleerd (zoals priemgetallen zelf, en modulo rekenen). Ook helpt het niet zo zeer mee dat ik nu probeer een mersenne-priem checker te maken (en begrijpen hoe) onder C++, waar ik pas een paar dagen geleden serieus mee begonnen ben. ik heb nu wat rond gekeken onder andere talen die ik wel snap, en heb op zo een goede procedure gevonden om priem-getallen te checken. die heb ik, door middel van trial&error, en nog belangrijker: tutorials en function-documentation, vertaald naar een C++ console application.
Hier is de source-code:

code:

# include <cmath>
# include <iostream>
using namespace std;
void priemcheck(long double);
int main()
{
long double tot = 0;
cout<<" tot: ";
cin>> tot;
cout<<"\n priemgetallen tot "<<tot<< ",";
priemcheck(tot);
return 0;
}
void priemcheck(long double tot)
{
     int vanaf;
     cout<<" vanaf: ";
     cin>> vanaf;
    bool priem = true; 
    int nummer;
     nummer =(int) floor (sqrt (tot));
    for ( ; vanaf <= tot; vanaf++)
    {       
        for ( int check = 2; check <= nummer; check++)
        {
            if ( vanaf!=check && vanaf % check == 0 )
            {      
                priem = false;
                break;
            }
        }
        if (priem)
        {
            cout <<"\n"<<vanaf<<" ";
        }
        priem = true;
    }
    cout << "\n";
    system("pause");
}

Dit opzich is nog niet te moeilijk, maar ik kan maar niet snappen hoe je een mersenne-priem herkent! Dus eerst wil ik jullie vragen hoe je dat nou helemaal checkt (wikipedia helpt me daar ook niet egt bij) en als ik er dan nog niet uitkom, weet ik in ieder geval waar ik naar toe moet gaan voor degelijke hulp

Alvast bedankt!

[DataGhost]

http://en.wikipedia.org/wiki/Mersenne_prime
nee, heel moeilijk inderdaad. Verder zijn Mersenne-priemgetallen nogal _groot_ over het algemeen, wat ook de lange tijd verklaart tot de 44e bekend was. Die tijd is zelfs flink verkort door het gebruik van gigantisch veel computers en een *iets* complexer stuk software dan wat jij geschreven hebt. Je moet je in elk geval niet teveel voorstellen van je programma, zeker niet op 1 pc.
(verder begrijp ik je code niet helemaal, je probeert een paar vreemde kunstgrepen uit te halen als ik het zo even vlug bekijk. Probeer je wat meer in te lezen in priemgetallen enzovoorts, voordat je willekeurig wat code begint op te schrijven. Verwacht ook geen wonderen, en al zeker niet de ontdekking van het 45e Mersenne-priemgetal. Het 44e heeft al bijna 10 miljoen decimalen, waar het 43e er 9 miljoen heeft. Ik denk dat het een klein beetje buiten een double long valt En natuurlijk niet te vergeten ben jij niet de enige die eens zin krijgt dat priemgetal te berekenen, er zijn een heleboel wetenschappers met hetzelfde doel, een hoop computers en een berg geld bezig )

[ Voor 44% gewijzigd door DataGhost op 19-09-2006 21:03 ]

[.oisyn]

Je doet het ook verkeerd om. Als van een priemgetal wilt weten of het een mersennepriem is, moet je kijken of ie aan de 2^p-1 conditie voldoen, waarbij p een priemgetal is. Dat is vrij lastig te bepalen. Makkelijker is om gewoon naar mersennepriemen te zoeken, oftewel gewoon alle 2^p-1 aflopen waarbij p én het resultaat priemgetallen zijn.

[link0007]

Ooh je hebt het dan ook verkeerd begrepen: ik probeer niet -nja, nog niet op mun 15e- het 45ste mersenne priem te vinden, enkel het weten hoe grijpt mij nu aan. En een groot deel van het mechanisme had ik ergens in een PASCAL tutorial gevonden, daarna een beetje mee gespeeld, en toen was het me duidelijk Maar hoe je dat in mersennes ombouwt? En zoals ik al zei: die wikipedia dingen zijn alien voor mij, ik heb veel van die wiskundige tekens nog niet eens behandelt!

[link0007]

*was een reactie op dataghost btw*

[Tutti-frutti]

DataGhost schreef op dinsdag 19 september 2006 @ 20:58:
Verwacht ook geen wonderen, en al zeker niet de ontdekking van het 45e Mersenne-priemgetal. Het 44e heeft al bijna 10 miljoen decimalen, waar het 43e er 9 miljoen heeft. Ik denk dat het een klein beetje buiten een double long valt En natuurlijk niet te vergeten ben jij niet de enige die eens zin krijgt dat priemgetal te berekenen, er zijn een heleboel wetenschappers met hetzelfde doel, een hoop computers en een berg geld bezig )

Priemgetallen met decimalen ?

[link0007]

je snapt toch wat 'ie bedoelt
maar ik weet zelf ook het nederlandse woord niet eerlijk gezegt... ik noem ze altijd gewoon "digits"

[DataGhost]

Tutti-frutti schreef op dinsdag 19 september 2006 @ 21:26:
[...]

Priemgetallen met decimalen ?

de·ci·maal1 (de ~, -malen)
1 elk van de eenheden in het decimale stelsel, kleiner dan één

heh. ja ik bedoel dus die groter dan 1 digits idd
cijfers klinkt zo lam

[ Voor 6% gewijzigd door DataGhost op 19-09-2006 21:38 ]

[.oisyn]

Cijfer is wel de correcte term

[link0007]

egt waar? klinkt anders niet zo ^_^
anyway, kan iemand me nou nog uitleggen hoe je kan zeggen dat een bepaald priemgetal een mersenne is?

[NMe]

Dat zegt .oisyn toch al? "Alle" priemgetallen aflopen, en daarbij kijken of 2^P - 1 ook een priemgetal is.

[.oisyn]

Heb je mijn reactie wel gelezen?

.edit: dat zeg ik toch -NMe-

[ Voor 26% gewijzigd door .oisyn op 19-09-2006 21:46 ]

[Swaptor]

.oisin heeft heel duidelijk opgeschreven wat een mersenne priemgetal is, een priemgetal wat voldoet aan de eis 2^p-1 waarbij p een priemgetal is.

je zult dus een 'lijst' moeten hebben van priemgetallen die als p fungeren, en voor iedere p 2^p-1 gaan uitrekenen en dit getal checken op het feit of het een priem is.

Machtverheffen en dergelijke heb je toch wel al gehad in 4HAVO hoop ik (ook al ben je nog maar net begonnen)

[ Voor 0% gewijzigd door Swaptor op 19-09-2006 21:47 . Reden: Zo dan, spuit 12 hiero! ]

[NMe]

Swaptor schreef op dinsdag 19 september 2006 @ 21:46:
je zult dus een 'lijst' moeten hebben van priemgetallen die als p fungeren, en voor iedere p 2^p-1 gaan uitrekenen en dit getal checken op het feit of het een priem is.

Zelfs die lijst is niet noodzakelijk; althans, die lijst is makkelijk zelf in code te genereren. De eerste functie die ik schreef voor een opdracht op het HBO was een IsPriem-functie; op HAVO 4-niveau moet dat ook wel te doen zijn.

Ook het opzoeken wat een modulo nu eigenlijk is en hoe die werkt moet voor een havist best te doen zijn trouwens. De topicstarter wéét blijkbaar dat modulo nodig is voor de gangbare oplossing, dan is het toch een kleine moeite om te kijken hoe die modulo werkt?

[ Voor 20% gewijzigd door NMe op 19-09-2006 21:51 ]

[MrBucket]

Let er wel op dat de datatypes die door de meeste programmeertalen worden ondersteund maar een beperkt bereik hebben. Zo is het 'int' datatype op de meeste systemen 32 bits, wat neerkomt op een maximum waarde van 2^32 = ong. 4,3 miljard (of 2,1 miljard als je ook negatieve getallen wilt kunnen opslaan).
Als je C/C++ compiler een 64-bits datatype ondersteunt (meestal 'long' genoemd, geloof ik), dan kan je met getallen tot 2^64 (= 10^19) werken.

Wil je met grotere getallen aan de slag, dan is het misschien handig om eens naar java te kijken, die kent het BigInteger datatype dat in principe gehele getallen van onbeperkte grootte aankan.
Een alternatief is het GNU-tooltje BC (Binary calculator), waarmee je in een soort van C-scripttaal ook kan rekenen met getallen van onbeperkte grootte.

[link0007]

ik heb wel opgezocht wat modulo is, en hoe ik hem moest gebruiken daarna (ik zag overal mod() staan in wiskundige formules, vindt het ook verdomd onlogisch dat deze functie niet bruikbaar is op de PC, enkel een % tekentje)
on the other hand, ik snap nu wel de vergelijking voor een mersenne beter (ik zweer het je, wiskunde tegenwoordig suckt gewoon, enkel grafieken en "hoe zet je je rekenmachientje aan" lessen -ik doe dan ook niet veel anders dan spelen met TI-basic, tot grote ergernis van mijn wiskunde leraar-)

[NMe]

MrBucket schreef op dinsdag 19 september 2006 @ 21:58:
Wil je met grotere getallen aan de slag, dan is het misschien handig om eens naar java te kijken, die kent het BigInteger datatype dat in principe gehele getallen van onbeperkte grootte aankan.

Er zijn ook verschillende BigInt-classes voor C++ beschikbaar op het internet, en zelf zo'n BigInt maken is natuurlijk ook niet al te moeilijk.

link0007 schreef op dinsdag 19 september 2006 @ 21:58:
ik heb wel opgezocht wat modulo is, en hoe ik hem moest gebruiken daarna (ik zag overal mod() staan in wiskundige formules, vindt het ook verdomd onlogisch dat deze functie niet bruikbaar is op de PC, enkel een % tekentje)

Dat heeft niks met "de PC" te maken, maar met de programmeertaal waar je mee werkt. In Pascal/Delphi noemen ze het bijvoorbeeld wel gewoon "mod".

on the other hand, ik snap nu wel de vergelijking voor een mersenne beter (ik zweer het je, wiskunde tegenwoordig suckt gewoon, enkel grafieken en "hoe zet je je rekenmachientje aan" lessen -ik doe dan ook niet veel anders dan spelen met TI-basic, tot grote ergernis van mijn wiskunde leraar-)

Wiskunde van vroeger zal echt niet veel beter geweest zijn. Je zal je zelf moeten inzetten om interessante dingen eruit te pikken en niet alleen maar bezig zijn met die dingen die je voor school moet doen. Ik heb hier op GoT persoonlijk meer geleerd dan in de klas.

[ Voor 53% gewijzigd door NMe op 19-09-2006 22:01 ]

[link0007]

Wie niet denk ik zo ^_^
Maar waarom we op school geen nummer-theorie krijgen? ik vind het maar een trieste zaak hoor...

[Soultaker]

Een naïeve priemtest is al snel O(sqrt(N)), oftewel, om te testen of een getal N priem is, moet je wortel-van-N operaties uitvoeren. Dat is voor een beetje Mersenne-getal absoluut onmogelijk. Gelukkig is er voor Mersenne-getallen een speciale priem test, de Lucas-Lehmer test; die wordt dan ook voor GIMPS gebruikt.

Meer informatie over Mersenne-priemgetallen is hier te vinden: http://primes.utm.edu/mersenne/index.html
Maar het is allemaal niet echt beginnersmateriaal. Begin maar eens met een gewone priemtest en de zeef van Eratosthenes.

offtopic:
Populair topic dit.

[MrBucket]

-NMe- schreef op dinsdag 19 september 2006 @ 21:59:
[...]

...en zelf zo'n BigInt maken is natuurlijk ook niet al te moeilijk.

Hehe, dat dacht je maar.

Jij en ik zouden het wel kunnen. Het schrijven van een simpele implementatie is een werkje, een efficiente implementatie is een behoorlijk werkje, en een efficiente, goed ge-unittestte implementatie is helemaal een klus op zich.

Laat staan voor iemand die nog niet zo lang programmeert.

[link0007]

ja die lucas-lehmer dingen heb ik ook doorgenomen, maar jullie begrijpen egt niet hoe iemand niet alles van wiskunde snapt... zijn die getallen echt zo moeilijk dan? vroeger deden ze die uit het hoofd, dus zo ingewikkeld kan het allemaal niet zijn, toch?

[link0007]

en een lange lijst tekens maken lijkt me vrij makkelijk als je gewoon naar een bestand schrijft... maar of het snel is?

[Wolfboy]

Mersenne priemgetallen worden niet echt uit het hoofd gedaan, daar zijn de meesten te groot voor, 3, 7, 31 en 127 gaan nog wel, maar daarna begint het toch snel uit de hand te lopen hoor

Je kijkt of iets een mersenne priemgetal is door het getal + 1 te nemen, te kijken of dat een macht van 2 is, en daarbij te kijken of het exponent een priemgetal is.
Dus bij 31 bijvoorbeeld, 31+1 = 32 = 2^5, 5 is een priemgetal en 31 ook dus is het een mersenne priem.

Ik neem aan dat je wel weet wat een exponent is? (zo niet, 2 tot de macht 5 is 2*2*2*2*2 = 32 dus )

[MrBucket]

Probeer eens de GNU Binary Calculator voor windows. Deze is te vinden op http://sourceforge.net/project/showfiles.php?group_id=23617 onder de naam "bc".

Je kan er met getallen van onbeperkte grootte werken, en je kunt er ook programmaatjes mee schrijven in een scripttaal die veel lijkt op C.

--edit--
Voorbeeldcode van een BC-programmaatje om een bepaald Fibonacci-getal uit te rekenen:

code:

define fibonacci(getal){
  if(getal < 2){
    return getal;
  }else{
    return fibonacci(getal - 1) + fibonacci(getal - 2);
  }
}

De vraag "print fibonacci(10)" geeft dan het 10e element uit de fibonacci-reeks: 55.

[ Voor 39% gewijzigd door MrBucket op 19-09-2006 22:34 ]

[Soultaker]

(Ik zou dan eerder zeggen, gebruik Python, met standaard integers van onbeperkte grootte. Java kan natuurlijk ook met z'n BigInteger klasse, maar dat geeft wat meer rompslomp.)

[link0007]

@ wolfboy:

ja exponenten hebben we gehad ja ZO slecht zijn de scholen van tegenwoordig nou ook weer niet

lijkt een redelijk duidelijke beschrijving btw... dus in feite zou je gewoon kunnen zeggen


priembegin+1=priembehandeling;
for ( ; exponent<=priembegin ; exponent++)
{
if (pow(2,exponent)==priembehandeling)
{
mersenne=true;
cout << priembegin
break;
}
}
(ruw gezegt dan, natuurlijk moet de code nog een beetje opgeschoond en bewerkt worden)

klopt dit zo? ut begint redelijk laat te worden voor mijn doen, dus egt helder denken kank nie meer

[Paul C]

Ik ben hier zelf ook wel eens ooit mee bezig geweest. Ik zal een stuk PHP code met je delen dat ik gemaakt heb. Ik heb het ooit geport naar C# en dat was vééééél sneller, maar dat heb ik nou echt geoptimaliseerd en hiervan ben ik redelijk overtuigd dat het best efficiënt is:

PHP:

$priemlist[1] = 3;                              // de lijst met priemgetallen, 2 niet, dat is even, die testen we niet
$mod = 0;                                       // de modulus van de deling, als deze 0 is hebben we een priem
$count = 1;                                     // teller van het aantal priemgetallen, tevens pointer van de priemlist
$testmax = 1;
$tests = 0;

// BEGIN PRIEM-ZOEK-CODE
for($i = 5; $i <= 500000; $i++){                // dit is het bereik van de getallen die hij test
    $test = 0;
    do{
        $mod = $i % $priemlist[++$test];        // testgetal testen met bekende priemgetallen
    } while($mod != 0 AND $priemlist[$test] <= $testmax);
    if($mod != 0){                              // checken of testmax bereikt is (priem) ofdat $mod = 0 true is
        $priemlist[++$count] = $i;              // pointer/counter ophogen en priem toevoegen aan de lijst
        $testmax = sqrt($i);                    // floor(sqrt($i)) is niet (substantieëel) sneller
    }
    $i++;                                       // om alle even getallen over te slaan (sneller dan $i = $i + 2) in de for loop
}
// EINDE PRIEM-ZOEK-CODE

Succes ermee iig.

[djc]

DataGhost schreef op dinsdag 19 september 2006 @ 20:58:
nee, heel moeilijk inderdaad. Verder zijn Mersenne-priemgetallen nogal _groot_ over het algemeen, wat ook de lange tijd verklaart tot de 44e bekend was.[/small])

Dit is onzin. Mersenne-priemgetallen zijn niet noodzakelijk groot, er zijn er alleen niet zoveel (lage dichtheid, op de natuurlijke getallen), dus je komt snel bij grotere getallen.

Soultaker schreef op dinsdag 19 september 2006 @ 22:32:
(Ik zou dan eerder zeggen, gebruik Python, met standaard integers van onbeperkte grootte. Java kan natuurlijk ook met z'n BigInteger klasse, maar dat geeft wat meer rompslomp.)

Volgens mij heb je bij dit soort reken-intensieve code wel te maken met een vrij grote performance hit als je van C/C++ (compiled in het algemeen) naar Python (of interpreted in het algemeen) gaat. Maar dat is misschien een premature optimization; je algoritmen zijn waarschijnlijk wel een stukje leesbaarder als je het in Python doet.

[jnice]

tjah, als je net begint enzo is dit misschien grappig, ik leer net zelf sinds een weekje C:

code:

#include <stdio.h>
#include <math.h>
#define iteraties 5000
main()
{
      double i,p[iteraties],c;
      int priem=1,n=0,n2;
      for(i=3;i<iteraties;i=i+2)
      {
                         for(c=2;c<i;c++)
                         {
                         if(fmod(i,c)==0.)
                         {priem=0; break;}
                         }
     if(priem==1)
     {
                 p[n]=i;
                 n++;
     }
     else
     {priem=1;}
     }
     printf("Priemgetal 1 is 1\n");
     printf("Priemgetal 2 is 2\n");
     for(n2=0;n2<n;n2++)
     {
                      printf("Priemgetal %d is %.0f\n",n2+3,p[n2]);
                      } 
     printf("druk op een toets om af te sluiten");
     getchar();
     }

Ik denk dat je de code wel begrijpt als je er even naar kijkt
Misschien is het ook wel te makkelijk voor je.

EDIT:
Het programma hierboven kan nogal wat sneller, twee dingen verandert:
1. de waarde i loopt nu vanaf 3 met i=i+2
2. er is een break; toegevoegd in de for loop

[ Voor 12% gewijzigd door jnice op 20-09-2006 00:13 ]

[link0007]

@ pcmadman: ik heb zelf ook al een priem-checker, alleen mersennes en andere priem-getallen ontbreken nog

@manuzhai: volgens mij is C toch egt een snelle taal ja... heeft iemand trouwens al egt naar mijn codes gekeken/ingevoerd/gekeken wat het deed? het is toch best een goede priem-checker

en kan iemand me zeggen of de code die ik in mijn laatste post gaf, een mersenne checker is?

[link0007]

en @jann1s: best een degelijke priem-checker... maar je kan ook

code:

system("pause");

gebruiken ipv handmatig "druk op een toets op af te sluiten" te doen...
al is wat ik gebruik C++ en geen C#, dus ik weet het verschil nie...

[NMe]

link0007 schreef op dinsdag 19 september 2006 @ 22:58:
en @jann1s: best een degelijke priem-checker... maar je kan ook

code:

system("pause");

gebruiken ipv handmatig "druk op een toets op af te sluiten" te doen...

offtopic:
Ja, en dan meteen crossplatform-functionaliteit op je buik schrijven.

[link0007]

pff, ik denk niet dat iemand hier zun priem-checker gaat verspreiden ofso ^_^ en zelfs als ze het zouden verspreide, zal het alleen gaan om hulp, of als tutorial... en het merendeel gebruikt toch gewoon windows, dus....

[DataGhost]

Manuzhai schreef op dinsdag 19 september 2006 @ 22:52:
[...]
Dit is onzin. Mersenne-priemgetallen zijn niet noodzakelijk groot, er zijn er alleen niet zoveel (lage dichtheid, op de natuurlijke getallen), dus je komt snel bij grotere getallen.

Mja, daarom zeg ik ook 'over het algemeen', dwz. volgens mij zijn slechts de eerste 9 Mersenne-priemen te berekenen met een int64, daarna heb je grotere datatypes nodig die niet direct voorhanden zijn (en qua tijd vraag ik het me ook af). Waar ik echter vanuit ging is dat de TS graag veel van die dingen wilde berekenen en dus 'al gauw' voorbij de 9 komt.

link0007 schreef op dinsdag 19 september 2006 @ 23:02:
pff, ik denk niet dat iemand hier zun priem-checker gaat verspreiden ofso ^_^ en zelfs als ze het zouden verspreide, zal het alleen gaan om hulp, of als tutorial... en het merendeel gebruikt toch gewoon windows, dus....

offtopic:
Nofi, maar zou je iets aan je taalgebruik kunnen doen? Je 'hippe' spelling leest nogal irritant, het zou een qua leesbaarheid een stuk schelen als je je post even nakijkt voordat je op 'Verstuur bericht' drukt. Verder begrijp ik niet erg veel van je zin en redenatie, maar dat zal aan mij liggen.

[ Voor 33% gewijzigd door DataGhost op 19-09-2006 23:17 ]

[link0007]

ow nee hoor, alleen al weten dat mijn logica correct is zou al goed zijn het is niet zozeer wat ik ermee kan, meer de prestatie opzich van het snappen en leren van C++ en wiskunde

[RobIII]

offtopic:
Wil je egt eens ophouden om egt met een g te schrijven?
Verder kun je je vorige post editten met de -knop als er na je vorige post nog niemand gereageerd heeft. Dan hoef je niet steeds binnen twee minuten je topic opnieuw te kicken (zie posts van 21:15 en 21:23, 22:13 en 22:14, 22:56 en 22:58). Lees ook dit even.

[ Voor 8% gewijzigd door RobIII op 19-09-2006 23:22 ]

[DroogKloot]

link0007 schreef:
en kan iemand me zeggen of de code die ik in mijn laatste post gaf, een mersenne checker is?

Nee, je checkt namelijk totaal niet of het getal en de exponent priem zijn, alleen maar of (n + 1) = 2^exponent, waar je nog geen conclusies aan kunt verbinden. Een Mersenne-checker werkt zo:

C:

int isMersennePrime(int n) {
    n += 1;
    e = 0;

    while ((1 << e) <= n) {
        if ((1 << e) == n)
            break;
        e++;
    }

    return (isPrime(e) && isPrime(n));
}

Optimalisaties (zoals controleren of de startwaarde (n + 1) uberhaupt wel een macht van 2 is, waardoor je die hele loop niet nodig hebt) mag je zelf bedenken.

[ Voor 13% gewijzigd door DroogKloot op 19-09-2006 23:50 . Reden: vaut in code :+ ]

[.oisyn]

Snel testen of een getal een macht van 2 is:

C++:

bool isPowerOfTwo(unsigned i)
{
    return (i & (i - 1)) == 0;
}

(0 geeft hier echter ook true terug, als je dat niet wilt zul je daar even expliciet op moeten controleren)

[ Voor 28% gewijzigd door .oisyn op 19-09-2006 23:37 ]

[Wolfboy]

Voor als mersenne getallen iets te lastig zijn om mee te beginnen, hier is een voorbeeldje van hoe je met python priemgetallen kunt vinden (doormiddel van de zeefmethode)

Python:

# tot welk nummer je wilt zoeken
MAX = 100

# een lijst maken met nummers
numbers = [2]
# kleine optimalisatie, alle even getallen op 2 na zijn sowieso geen priemgetallen
numbers[1:] =  range(3, MAX, 2)

# een lege lijst maken voor de priemgetallen
primes = []

# doorgaan tot numbers leeg is
while len(numbers) > 0:
    # het eerste getal van numbers toevoegen aan de lijst met priemgetallen
    primes.append(numbers[0])

    # de lengte van numbers bepalen zodat we alle getallen kunnen testen
    i = len(numbers) - 1

    # door alle getallen in numbers heen lopen
    while i >= 0:
        # kijken of het getal een veelvoud van ons getal is
        if numbers[i] % primes[-1] == 0:
            # verwijder het getal uit de lijst
            numbers.pop(i)

            # het getal met 2 verlagen (aangezien we een getal verwijderd hebben moeten we 2 plaatsen terug)
            i -= 2
        else:
            # het getal met 1 verlagen
            i -= 1

[Paul C]

link0007 schreef op dinsdag 19 september 2006 @ 22:56:
@ pcmadman: ik heb zelf ook al een priem-checker, alleen mersennes en andere priem-getallen ontbreken nog

Dat het ik ook wel gezien, maar mijn algoritme is een stuk efficiënter dan dat van jou.

Je kunt jou programma een heel stuk sneller maken door een heleboel dingen niet te testen waarvan je toch zeker weet dat ze false retourneren. Zo hoef je bijv. alleen de mod te berekennen van alle priemgetallen kleiner dan of gelijk aan de wortel van het te testen getal.

Tevens kun je je programma al bijna 50% sneller maken door alleen vanaf++; toe te voegen, zodat je alle even getallen overslaat bij het testen. Wat als logisch gevolg heeft dat je niet meer met 2 hoeft te beginnen met testen, maar met 3, wat ook weer een flinke performanceboost is als je mijn eerste tip geimplementeerd hebt.

[EdwinG]

Kan iemand mij zeggen waarom 2³⁷ -1 geen mersenne priem is?
Volgens mij zijn zowel 37 als de uitkomst ( 137438953471 ) priemgetallen. (ik kan in ieder geval geen deler van het laatste getal vinden.)

[JackBol]

Als je werkelijk al in 4Havo zit, schrijf dan voortaan 'echt' met een 'ch'. Want egt haalt het bloed onder mijn nagels vandaan.


Verder geef je al meerdere malen aan dat je weinig van (hogere) wiskunde begrijpt. Dan word het erg lastig voor je om een vrij lastig vraagstuk als het zoeken naar mersenne priemgetallen aan te pakken.

Er zijn vervolgens een paar praktische zaken waar je tegenaan loopt:

Ten eerste moet je een priemgetal vinden (heel vaak O(sqrt(N)) op jou manier). Vervolgens wil je twee tot de macht priem doen en er 1 vanaf trekken. Oftewel, je getal word groter. Vervolgens moet je weer een priemtest doen, maar nu op een veel groter getal.
Je moet dus ERG veel rekenen. Het is fijn als je dit snel kan doen. Oftewel, een geinterpreteerde taal gaat moeilijk worden. C zou voorkeur hebben en als het in ASM kan, zou het helemaal fijn zijn. Verder moet je grote getallen op kunnen slaan in je geheugen, maar een getal met 9 biljoen cijfers is toch 9 gig geheugen. Je zal dus trucjes moeten uithalen om met deze getallen te kunnen werken.


Maar het beste advies is toch het volgende:

Programmeren is niet code kloppen. Programmeren is een algoritme bedenken dat je probleem (effectief en efficient) oplost. Het is dus vele malen belangrijker dat je eens rustig gaat zitten en je in de materie verdiept. Er zijn namelijk heel wat slimme foefjes die je uit kan halen met priemgetallen. Als je vervolgens goed in je kop hebt wat je wilt bereiken en hoe je het wilt doen, kun je het algoritme programmeren in een taal die daar het meest geschikt voor is, om vervolgens je probleem op te lossen.

[JackBol]

EdwinG schreef op dinsdag 19 september 2006 @ 23:56:
Kan iemand mij zeggen waarom 2³⁷ -1 geen mersenne priem is?
Volgens mij zijn zowel 37 als de uitkomst ( 137438953471 ) priemgetallen. (ik kan in ieder geval geen deler van het laatste getal vinden.)

223

[EdwinG]

Dan
1: Is mijn gebruik van de % operator in php verkeerd
2: kan php niet goed met getallen boven 2³² omgaan
3: heb ik last van slecht geheugen/processor

PHP:

$x = $getal % $j;
echo $getal . ' % ' . $j . ' = ' . $x . '<br />';

Levert:
137438953471 % 223 = 114

[DataGhost]

EdwinG schreef op woensdag 20 september 2006 @ 00:18:
Dan
1: Is mijn gebruik van de % operator in php verkeerd
2: kan php niet goed met getallen boven 2³² omgaan
3: heb ik last van slecht geheugen/processor

PHP:

$x = $getal % $j;
echo $getal . ' % ' . $j . ' = ' . $x . '<br />';

Levert:
137438953471 % 223 = 114

http://nl3.php.net/manual/nl/language.types.integer.php
ik ga voor optie 2, had je eigenlijk wel moeten/kunnen weten

dataghost@helios ~ $ cat groot.php && php groot.php
<? $getal=137438953471; var_dump($getal); $getal = (int) $getal; var_dump($getal); ?>
float(137438953471)
int(-1)

modulo werkt met integers, niet met floats

[ Voor 17% gewijzigd door DataGhost op 20-09-2006 00:27 ]

[.oisyn]

Puntje 2 dus

[jnice]

Sorry als ik het topic onnodig omhoog kick, maar ik vind C wel leuk
Voor de meneer/mevrouw die zich afvroeg of het getal een priemgetal is, heb ik een kort stukje code geschreven:

code:

#include <stdio.h>
#include <math.h>
main()
{
      int priem=1,i;
      double a,b,c=0;
      printf(" Voer het vermeende priemgetal in:\n");
      scanf("%lf",&a);
      for(i=2;i<a;i++)
      {
                      
                       b=i;
                       if(fmod(b,10000000)==0.)
                       {c=100.*b/a; printf("Voor %.1lf  klaar\n",c);}
                       if(fmod(a,b)==0.)
                       {priem=0; break;}
                       }

if(priem==1)
{printf(" Het getal %.0lf is een priemgetal!\n",a);}

else
{
    printf(" Het getal %.0lf is geen priemgetal :(\n",a);
    printf(" Het getal %.0lf is deelbaar door %.0f\n",a,b);}

printf(" Druk op enter om af te sluiten\n");
getchar(); getchar();
}

Op mijn pc werkt het wel aardig ook met grote getallen (2^50 oid), verder heb ik niet echt onderzocht.
Trouwens, misschien weet iemand of ik gelijk heb ik dat ik b=i; gebruik. Dit omdat ik vermoed dat integers beter in een for loop kunnen staan (geen afwijkingen in een integer).
Kleine update, het programma laat nu de voortgang zien, wel zo handig voor grote priemgetallen.
(Probeer bijvoorbeeld eens 2^31-1, snel gaat het niet, maar iig sneller dan Euler )

[ Voor 13% gewijzigd door jnice op 20-09-2006 01:01 ]

[NMe]

fmod? Je gebruikt floating point math om te zien of iets een priemgetal is? Lekker onzinnig, aangezien priemgetallen per definitie integers zijn.

[Wolfboy]

Hier een iets nettere versie van je stukje code jann1s

C:

#include <stdio.h>
#include <math.h>

main(){
    long i,input;
    printf(" Voer het vermeende priemgetal in:\n");
    scanf("%li",&input);
    for(i=2; i<input; i++){
        if(input % i ==0)break;
    }

    if(i == input){
        printf(" Het getal %li is een priemgetal!\n", input);
    }else{
        printf(" Het getal %li is geen priemgetal :(\n", input);
        printf(" Het getal %li is deelbaar door %li\n", input, i);
    }
    printf(" Druk op enter om af te sluiten\n");
    getchar();
}

[jnice]

Wolfboy, bedankt voor je reactie, zo leer ik nog eens wat!
Ik heb nog wat dingen veranderd aan jouw verbeteringen, zodat 1 ook wordt gezien als priemgetal, en de for loop alle even getallen overslaat. Die tweede getchar() moet er bij mij staan, anders sluit hij meteen af (herkent vorige enter??).

code:

#include <stdio.h>
#include <math.h>

main(){
    long i,input;
    printf(" Voer het vermeende priemgetal in:\n");
    scanf("%li",&input);
    if(input % 2 == 0)
    {i=2;}
    else if(input==1)
    {input=i=1;}
    else
    {
    for(i=3; i<input; i=i+2)
    {
        if(input % i ==0)break;
        if(i % 10000001 ==0)printf("%.2f %% voltooid\n",100.*i/input);
    }
    }

    if(i == input)
    {
        printf(" Het getal %li is een priemgetal!\n", input);}
    else
    {
        printf(" Het getal %li is geen priemgetal :(\n", input);
        printf(" Het getal %li is deelbaar door %li\n", input, i);}
    
    printf(" Druk op enter om af te sluiten\n");
    getchar(); getchar();
}

Dan nog een laatste opmerking: Op mijn computer kan dit programma qua functionaliteit niet op tegen het programma met floats. Het is wel sneller, maar kan met minder grote getallen werken.
Bijvoorbeeld dat (2^53 - 1) = 9007199254740991 deelbaar is door 6361.
Daarom vind ik (hoe slecht het dan ook moge zijn) het eerste programma niet volledig "onzinnig".

[ Voor 14% gewijzigd door jnice op 20-09-2006 01:45 ]

[Wolfboy]

jann1s schreef op woensdag 20 september 2006 @ 01:39:
Wolfboy, bedankt voor je reactie, zo leer ik nog eens wat!
Ik heb nog wat dingen veranderd aan jouw verbeteringen, zodat 1 ook wordt gezien als priemgetal, en de for loop alle even getallen overslaat.

1 is geen priemgetal

Die tweede getchar() moet er bij mij staan, anders sluit hij meteen af (herkent vorige enter??).

Je zal de buffer eventjes moeten flushen, als je eventjes zoekt in de GoT database of bij Google dan zal je wel meer mensen met dat probleem vinden.

Dan nog een laatste opmerking: Op mijn computer kan dit programma qua functionaliteit niet op tegen het programma met floats. Het is wel sneller, maar kan met minder grote getallen werken.
Bijvoorbeeld dat (2^53 - 1) = 9007199254740991 deelbaar is door 6361.
Daarom vind ik (hoe slecht het dan ook moge zijn) het eerste programma niet volledig "onzinnig".

Dat hangt helaas af van hoe groot een long is bij jouw C compiler, kijk eventjes in het bestand limits.h voor de exacte grootte.

Maargoed, om wat grotere getallen toe te laten kan je 'unsigned long int' gebruiken, om in ieder geval nog een iets groter getal te krijgen, eventueel zou zelfs nog een 'unsigned long long int' kunnen waarmee je een nog groter getal kan krijgen (mits de compiler het ondersteund).

Het maximum wat GCC bij mij wil doen is 18446744073709551615.

[link0007]

Nou, bedankt voor al jullie antwoorden
Was ook weer een leuke klus om doorheen te lezen.
Dat jullie problemen hebben met mijn taalgebruik (alhoewel het maar 1 letter verschil is, die in feite ook nog geen andere uitspraak/betekenis geniet) spijt mij dan ook. Ik zal er vanaf nu op letten dat ook de senioren mij kunnen verstaan. Ik denk dat ik jullie advies maar eens opvolg, eerst eens een ander programma proberen te schrijven, en dan -wanneer ik wiskunde afgerond heb- weer verder gaan met interessante zaken, zoals nummer-theorien (sorry, maar die accenten werken niet op mijn toetsenbord).
Toch bedankt voor al jullie uitleg en voorbeelden, maar ik denk niet dat er -op droogkloot's voorbeeld na- veel 'nuttigs' uit dit topic is gekomen, het merendeel van de mensen heeft waarschijnlijk het topic niet gelezen -of begrepen-, en weet daarom niet dat ik niet iemand ben die op zoek is naar een priemgetal van 10miljoen getallen plus, enkel naar kennis, en ik dacht -hoopte- dat jullie dit wel zouden begrijpen, maar blijkbaar zijn jullie allemaal zo gefixeerd op de directe resultaten, in plaats van leren en dan pas verbeteren, dat het hier niet veel zin heeft om te vragen over uitleg naar priemfuncties en mersenne-checkers.
Maar nogmaals bedankt voor jullie hulp:)

[djc]

_DH schreef op dinsdag 19 september 2006 @ 23:57:
Als je werkelijk al in 4Havo zit, schrijf dan voortaan 'echt' met een 'ch'. Want egt haalt het bloed onder mijn nagels vandaan.

(...)

(heel vaak O(sqrt(N)) op jou manier)

Off-topic: schrijf dan voortaan 'jouw' als je het bezittelijk gebruikt. Want jou haalt het bloed onder mijn nagels vandaan.

[Nick The Heazk]

link0007 schreef op woensdag 20 september 2006 @ 07:56:Toch bedankt voor al jullie uitleg en voorbeelden, maar ik denk niet dat er -op droogkloot's voorbeeld na- veel 'nuttigs' uit dit topic is gekomen, het merendeel van de mensen heeft waarschijnlijk het topic niet gelezen -of begrepen-, en weet daarom niet dat ik niet iemand ben die op zoek is naar een priemgetal van 10miljoen getallen plus, enkel naar kennis [...] dat het hier niet veel zin heeft om te vragen over uitleg naar priemfuncties en mersenne-checkers.

Ik vind je uitleg best wel tegenstrijdig ... Je zit te roepen dat het enkel om de kennis te doen is, terwijl je het enige nuttige aan dit topic een concrete implementatie vindt . Verder negeer je deze post van .oisyn, -NMe-, nogmaals .oisyn, Swaptor en de enige efficiënte test voor grote Mersenne priemgetallen die werd aangedragen in deze post door Soultaker . De mensen die hier algoritmes aanbieden om priemgetallen te zoeken zijn - mijn inziens - niet off-topic bezig. Voor de Mersenne-tester die door .oisyn gesuggereerd werd, heb je namelijk eerst priemgetallen nodig.

Verder zou je ook nog eens kunnen zoeken op Mathworld naar Mersenne priemgetallen en naar de Lucas-Lehmer test.

[ Voor 13% gewijzigd door Nick The Heazk op 20-09-2006 11:49 ]

[WVL_KsZeN]

.oisyn schreef op dinsdag 19 september 2006 @ 23:36:
Snel testen of een getal een macht van 2 is:

C++:

bool isPowerOfTwo(unsigned i)
{
    return (i & (i - 1)) == 0;
}

\o/ lang leve het binaire stelsel! Dit zou je niet zo makkelijk kunnen doen in een ander stelsel, had het zelf nog niet eens bedacht ... Maar dit werkt natuurlijk niet meer als je met een speciaal systeem moet gaan werken om met getallen > 2^32 of >2^64 om te gaan.. jammer.

[ Voor 9% gewijzigd door WVL_KsZeN op 20-09-2006 11:52 ]

[RobIII]

Hier heb je een stukje kennis:

Je hoeft niet van 1 (of 2) tot de waarde van "input" te "loopen" om te controleren of iets een priemgetal is. Een loop tot Wortel(Input) is al meer dan voldoende *

Waarom dat zo is mag je zelf uitvogelen (simpele wiskunde)

Maar dat is de kunst van het programmeren. Je algoritme dusdanig "slim" maken dat je algoritme ook nog eens bruikbaar wordt. Zo kun je alle even getallen overslaan, hoef je niet verder te checken dan Wortel(vermeend_priem) en zijn er nog een heleboel optimalisaties te bedenken. Wil je een uber-efficiënt algoritme dan zul je je toch echt meer in wiskunde dan programmeren moeten verdiepen. Zelfs top-coders schrijven zo'n algoritme niet zonder de benodigde kennis (en dat geldt uiteraard in het algemeen, niet alleen voor priemgetallen dus).

* Dat is overigens al meer gezegd in dit topic:
Soultaker in "Priemgetallen, in het bijzonder Mersenne..."
en
pcmadman in "Priemgetallen, in het bijzonder Mersenne..."

[ Voor 11% gewijzigd door RobIII op 20-09-2006 11:54 ]

[JackBol]

RobIII schreef op woensdag 20 september 2006 @ 11:53:
Hier heb je een stukje kennis:

Je hoeft niet van 1 (of 2) tot de waarde van "input" te "loopen" om te controleren of iets een priemgetal is. Een loop tot Wortel(Input) is al meer dan voldoende *

Waarom dat zo is mag je zelf uitvogelen (simpele wiskunde)

Maar dat is de kunst van het programmeren. Je algoritme dusdanig "slim" maken dat je algoritme ook nog eens bruikbaar wordt. Zo kun je alle even getallen overslaan, hoef je niet verder te checken dan Wortel(vermeend_priem) en zijn er nog een heleboel optimalisaties te bedenken. Wil je een uber-efficiënt algoritme dan zul je je toch echt meer in wiskunde dan programmeren moeten verdiepen. Zelfs top-coders schrijven zo'n algoritme niet zonder de benodigde kennis (en dat geldt uiteraard in het algemeen, niet alleen voor priemgetallen dus).

* Dat is overigens al meer gezegd in dit topic:
Soultaker in "Priemgetallen, in het bijzonder Mersenne..."
en
pcmadman in "Priemgetallen, in het bijzonder Mersenne..."

je kan ook zowiezo alle even getallen overslaan (snelle check: kijk even naar de laatste bit )

[RobIII]

_DH schreef op woensdag 20 september 2006 @ 11:58:
[...]


je kan ook zowiezo alle even getallen overslaan (snelle check: kijk even naar de laatste bit )

RobIII schreef op woensdag 20 september 2006 @ 11:53:
<snip>
Zo kun je alle even getallen overslaan
</snip>
...

[ Voor 22% gewijzigd door RobIII op 20-09-2006 12:03 ]

[crisp]

Sterker nog: een getal is priem als het niet deelbaar is door alle priemgetallen tot wortel n

Dus als n = 101 dan hoef je alleen maar te kijken of het deelbaar is door 2, 3, 5 of 7

[DaCoTa]

Wolfboy schreef op woensdag 20 september 2006 @ 01:07:
Hier een iets nettere versie van je stukje code jann1s
<KNIP>

Kleine toevoeging, voorbij de helft van input hoef je niet meer te checken. Dus de loop kan stoppen bij input / 2.

edit:
Argh, crips is slimmer

[ Voor 6% gewijzigd door DaCoTa op 20-09-2006 15:49 ]

[.oisyn]

Argh, crips is slimmer

Nee, want het is tot en met wortel n

[JackBol]

.oisyn schreef op woensdag 20 september 2006 @ 17:28:
[...]

Nee, want het is tot en met wortel n

dat lijkt mij sterk, want als sqrt(n) een geheel getal is, dan is n per defenitie te delen door sqrt(n)

[.oisyn]

Heel goed. En daarom moet je die dus óók controleren om te zeggen of iets priem is

[MSalters]

Helaas is wat jij vindt irrelevant. Met floats produceer je onzin. Snel onzin produceren is geen kunst. Zo is (2^53-1)==(2^53) met IEEE floats. En 2^53 is duidelijk geen priemgetal.

edit:
topic loopt te hard

[ Voor 7% gewijzigd door MSalters op 20-09-2006 20:45 ]

[Ivo]

Een python priemchecker zonder limieten aan getallen:

Python:

def is_prime(n):
  i = 2
  while(i*i<=n):
    if (not(n%i)):
      return False
    i+=1
  return True

Edit: .oisyn: Dat gebeurt me nu zo vaak als ik een while-lus gebruik waar ik in C een for-lus zou hebben gebruikt.

[ Voor 28% gewijzigd door Ivo op 23-09-2006 09:44 ]

[.oisyn]

Mooie infinite loop heb je daar

[Sibylle]

crisp schreef op woensdag 20 september 2006 @ 12:19:
Sterker nog: een getal is priem als het niet deelbaar is door alle priemgetallen tot wortel n

Dus als n = 101 dan hoef je alleen maar te kijken of het deelbaar is door 2, 3, 5 of 7

zo dus, waarbij je in het bestandje priem.dat alle priemgetallen tot "n" krijgt. Als je n vergroot moet je ook de grootte van de array veranderen (dus array_priem[n+1]).

code:

#include <stdio.h>
int n=1000,array_priem[1001],getallen=0,i,j;
FILE *priem;
void main(){
    for(i=0;i<n;i++){
        array_priem[i]=i;
        }
    
    for(i=2;i<=(n/i);i++){
        if(array_priem[i]!=0){
            for(j=2;j<=(n/i);j++){
            array_priem[i*j]=0;
                }
            }
        }
    
    
    priem=fopen("priem.dat","w");
    for(i=2;i<n;i++){
        if(array_priem[i]!=0){
            getallen++;
            fprintf(priem,"%d\n",array_priem[i]);
            }
        }
    fprintf(priem,"\nAantal priemgetallen: %d",getallen); 
    fclose(priem);
}

edit:
over alle priemgetallen tot de 100.000.000 doet hij ongeveer een halve minuut hier (schatting) en levert een .dat bestand van 55.5MB met ongeveer 15.000 pagina's.
Aantal priemgetallen: 5761455

Array size is alleen beperkt, dus moet je truucje uithalen om grotere getallen te willen. Mijn array kan niet tot de miljard bijvorbeeld:

priem.c - 1 error
2, 50 Size of 'array of unsigned int' exceeds 2147483647 bytes.

jammer.

[ Voor 20% gewijzigd door Sibylle op 22-09-2006 12:35 ]

[Voutloos]

Sibylle schreef op vrijdag 22 september 2006 @ 12:06:
[...]
zo dus, waarbij je in het bestandje priem.dat alle priemgetallen tot "n" krijgt.

Hoezo 'zo dus', je doet niet exact wat Crisp zegt, je bouwt namelijk de array van priemgetallen op door botweg alle factoren te doorlopen. Je kan de array ook opbouwen door te checken of $i deelbaar is door een element uit dat array.

edit:
Correctie: dat doe je wel min of meer dmv die conditie...

Dit had ik in PHP geimplementeerd en ik dacht dat het sneller zou zijn dan jouw aanpak, maar jouw aanpak 1 op 1 vertaalt naar PHP bleek 40% sneller (limiet had ik op 100.000).

Array size is alleen beperkt, dus moet je truucje uithalen om grotere getallen te willen. Mijn array kan niet tot de miljard bijvorbeeld:

priem.c - 1 error
2, 50 Size of 'array of unsigned int' exceeds 2147483647 bytes.

jammer.

Maar je kan de array ook aanmaken met alle elementen op 1, dan hoeft het ook geen array van unsigned ints te zijn. Op regel 22 kan je net zo goed i wegschrijven ipv de waarde van het element, dus je hoeft geen grote waardes in de elementen op te slaan. Verder kan je snelheid optimaliseren door in een aantal van de loopjes bij 3 te laten beginnen en steeds 'loopvar+=2' te doen, als je maar eenmalig de even getallen checkt. Tevens scheelt het ook als je de conditie van je loop 1x vlak voor de loop berekent.

[Soultaker]

offtopic:
Mooie command-line priem check met Perl:
perl -e 'print ((1x shift)!~/^(..+?)\1+$/ and Priem or Composite)' 123

[writser]

MrBucket schreef op dinsdag 19 september 2006 @ 22:27:
Voorbeeldcode van een BC-programmaatje om een bepaald Fibonacci-getal uit te rekenen:

code:

define fibonacci(getal){
  if(getal < 2){
    return getal;
  }else{
    return fibonacci(getal - 1) + fibonacci(getal - 2);
  }
}

De vraag "print fibonacci(10)" geeft dan het 10e element uit de fibonacci-reeks: 55.

Misschien wat off-topic, maard eze oplossing is zo inefficient dat ik er pijn van in mijn ogen krijg. Ik citeer Wikipedia:

Even on the worlds fastest supercomputer, IBM's Blue Gene/L, which clocks at 280.6 TFLOPS[2], to calculate f(100) would require at least 32 days.

Op de universiteit werd dit voorbeeld gebruikt als inleiding tot de informatica. Als je niks te doen hebt, bedenk dan eens waarom deze oplossing zo traag is. En hoe je het efficienter zou kunnen aapakken. Zie ook:

http://en.wikipedia.org/wiki/Fibonacci_number

[EdwinG]

Niet moeilijk om te bedenken wat er traag aan is.
Hoe hoger de invoer, hoe vaker deze functie zichzelf aanroept.

code:

Invoer  Loops
1       1
2       3
3       5
4       9
5      15

[Nick The Heazk]

Sibylle schreef op vrijdag 22 september 2006 @ 12:06:
zo dus, waarbij je in het bestandje priem.dat alle priemgetallen tot "n" krijgt. Als je n vergroot moet je ook de grootte van de array veranderen (dus array_priem[n+1]).

code:

[...]

Jou code bevat toch een aantal fouten hoor. Laten we even de eerste lus en de lus van de I/O buiten beschouwing. Je laat je buitenste lus maar zoeken tot i <= n/i. Dit wil zeggen dat je de priemgetallen in het interval [2, sqrt(n)] gaat zoeken in plaats van [2, n].
Edit: dom van me

Daarnaast heb je nog een subtiele array index fout gemaakt. Deze fout treed enkel op bij de priemfactoren van je variabele n. Indien je variabele i een priemfactor is van n, dan heb je een gehele deling bij n/i. Dit zorgt ervoor dat je variabele j net groot genoeg kan worden zodanig dat i * j gelijk is aan n, wat net buiten de array valt.

[jnice]

Op de volgende pagina's staat wat eenvoudige uitleg die misschien leuk voor je is, en tevens links (op de laatste pagina).

http://www.pythagoras.nu/mmmcms/public/artikel213.html

[DRAFTER86]

Even een vraagje, als ik wil weten of N een (normaal) priemgetal is moet ik kijken of het deelbaar is door een geheel getal kleiner of gelijk aan sqrt(N), dat snap ik. Maar is het ook niet zo dat ik alleen de priemgetallen kleiner of gelijk aan sqrt(N) hoef te proberen?

[ Voor 4% gewijzigd door DRAFTER86 op 24-09-2006 15:08 ]

[EdwinG]

Dat klopt inderdaad, controleren op priemgetallen kleiner dan of gelijk aan sqrt(N) is voldoende.
Als een getal deelbaar is door X, is het ook deelbaar door alle delers van X. Je hoeft dus alleen te controleren of je kunt delen door getallen, waarvan je nog geen delers gecontroleerd hebt. En dat zijn de priemgetallen, aangezien die geen delers hebben.

[Voutloos]

Nick The Heazk schreef op zaterdag 23 september 2006 @ 22:12:
Jou code bevat toch een aantal fouten hoor. Laten we even de eerste lus en de lus van de I/O buiten beschouwing. Je laat je buitenste lus maar zoeken tot i <= n/i. Dit wil zeggen dat je de priemgetallen in het interval [2, sqrt(n)] gaat zoeken in plaats van [2, n].

Ik las hem ook eerst verkeerd, maar het klopt wel. Alle getallen t/m sqrt(n) worden, indien ze priem zijn, gebruikt om grotere factoren weg te strepen.

[Nick The Heazk]

Voutloos schreef op zondag 24 september 2006 @ 16:37:
Ik las hem ook eerst verkeerd, maar het klopt wel. Alle getallen t/m sqrt(n) worden, indien ze priem zijn, gebruikt om grotere factoren weg te strepen.

Ik heb nogmaals nagedacht, en je hebt gelijk. De reden waarom ik misleid was, is omdat ik die I/O net achterwege heb gelaten. Echter de array index fout zou nog blijven bestaan.

[MrBucket]

writser schreef op zaterdag 23 september 2006 @ 13:02:
[...]

Misschien wat off-topic, maard eze oplossing is zo inefficient dat ik er pijn van in mijn ogen krijg. Ik citeer Wikipedia:

[...]

Op de universiteit werd dit voorbeeld gebruikt als inleiding tot de informatica. Als je niks te doen hebt, bedenk dan eens waarom deze oplossing zo traag is. En hoe je het efficienter zou kunnen aapakken. Zie ook:

http://en.wikipedia.org/wiki/Fibonacci_number

*Zucht*

Jij hebt de gedachte achter mijn post dus niet begrepen. Het ging erom dat het scripttaaltje in BC qua syntax behoorlijk veel op C lijkt. En dus heb ik een functie van een paar regels uitgewerkt om dat te demonstreren.

Niet om de meest bad-ass getweakte code neer te zetten die geweldig efficient is, maar waar niemand nog een snars van snapt.

[writser]

MrBucket schreef op zondag 24 september 2006 @ 17:22:
[...]

*Zucht*

Jij hebt de gedachte achter mijn post dus niet begrepen. Het ging erom dat het scripttaaltje in BC qua syntax behoorlijk veel op C lijkt. En dus heb ik een functie van een paar regels uitgewerkt om dat te demonstreren.

Niet om de meest bad-ass getweakte code neer te zetten die geweldig efficient is, maar waar niemand nog een snars van snapt.

*Zucht*

De topicstarter is gefascineerd door 'wiskundig programmeren', zoals hij zelf zegt. Daarom liet ik hem even een ander voorbeeld zien, naast de priemgetallen waar het topic over gaat. Misschien vind hij dat ook wel interessant. Je hoeft je niet meteen aangevallen te voelen omdat ik je aanspreek op de inefficientie van je code

[MrBucket]

Wat ook nuttig kan zijn is om algoritmes te gebruiken die bepalen of een getal probably prime is, zoals bijvoorbeeld Fermat's priemtest.

De test kent 2 mogelijke uitkomsten:
- Het getal is zeker niet priem
- Het getal zou priem kunnen zijn.

Als je de test meerdere keren uitvoert, en je krijgt constant het antwoord 'het getal zou priem kunnen zijn', dan is de kans groot dat dat ook inderdaad het geval is.

Het voordeel van deze (en soortgelijke) tests is dat het veel sneller is dan het daadwerkelijk factoriseren van getallen om aan te tonen dat ze niet priem zijn. Met deze test kun je dus efficient veel getallen elimineren als zijnde 'niet priem', en voor die paar die wel probably prime zijn, kun je een duurdere test doen (zoals factoriseren).

_{@writser: Je post kwam een beetje belerend op me over, vandaar. Maar no offence taken}

[ Voor 5% gewijzigd door MrBucket op 24-09-2006 17:48 ]

[PiepPiep]

MrBucket schreef op zondag 24 september 2006 @ 17:45:
Wat ook nuttig kan zijn is om algoritmes te gebruiken die bepalen of een getal probably prime is, zoals bijvoorbeeld Fermat's priemtest.

De test kent 2 mogelijke uitkomsten:
- Het getal is zeker niet priem
- Het getal zou priem kunnen zijn.

Als je de test meerdere keren uitvoert, en je krijgt constant het antwoord 'het getal zou priem kunnen zijn', dan is de kans groot dat dat ook inderdaad het geval is.

Het voordeel van deze (en soortgelijke) tests is dat het veel sneller is dan het daadwerkelijk factoriseren van getallen om aan te tonen dat ze niet priem zijn. Met deze test kun je dus efficient veel getallen elimineren als zijnde 'niet priem', en voor die paar die wel probably prime zijn, kun je een duurdere test doen (zoals factoriseren).

_{@writser: Je post kwam een beetje belerend op me over, vandaar. Maar no offence taken}

Over het algemeen klopt dit, alleen met mersenne getallen niet doordat daar een manier voor is om het zeker te weten of het wel of niet priem is.

[Sibylle]

Nick The Heazk schreef op zaterdag 23 september 2006 @ 22:12:
[...]


Jou code bevat toch een aantal fouten hoor. Laten we even de eerste lus en de lus van de I/O buiten beschouwing. Je laat je buitenste lus maar zoeken tot i <= n/i. Dit wil zeggen dat je de priemgetallen in het interval [2, sqrt(n)] gaat zoeken in plaats van [2, n].

Daarnaast heb je nog een subtiele array index fout gemaakt. Deze fout treed enkel op bij de priemfactoren van je variabele n. Indien je variabele i een priemfactor is van n, dan heb je een gehele deling bij n/i. Dit zorgt ervoor dat je variabele j net groot genoeg kan worden zodanig dat i * j gelijk is aan n, wat net buiten de array valt.

het interval is prima, de rest wordt gedekt door de procedure, want 500*2 = 1000, als ik ot de 2*1000 ga zit ik twee keer zo hoog als mijn n, en worden de laatste getallen toch niet meegenomen.

tweede kan kloppen, maar dat valt makkelijk te omzeilen bij juiste keuze van n lijkt me.

Tot de 100.000.000 heb ik iig ALLE priemgetallen gevonden, 100%. Ik heb namelijk bij de uitput ook gedaan hoeveel priemgetallen gevonden zijn. En toen met Maple (wiskunde programma) dat priemgetal gevonden, en het klopte.
(Dus bij 100.000.000 had ik x priemgetallen gevonden, invullen bij maple dat hij het x'de priemgetal teruggeeft (duurt ff ) en controleren of dat gelijk is aan het laatste getal in de output van mijn code. Bij alle n geprobeerd klopt het, maar ik heb alleen n=10,100,1000,100.000 etc.geprobeerd).

Bij welke n treedt de tweede fout dan op volgens jou? dat ga ik eens proberen.


edit: sorry, ik las net pas wat er bovenaan dze pagina staat
Maar in die array fout ben ik wel geintereseerd, kun je een voorbeeld noemen?

[ Voor 4% gewijzigd door Sibylle op 25-09-2006 21:34 ]

[Tomatoman]

Om priemgetallen te bepalen ben je al op de goede weg. Als je heel vaak controleert of getallen priemgetallen zijn (dus je functie heel vaak uitvoert), kost dat vrij veel rekentijd. Aangezien computers tegenwoordig erg snel zijn is dat meestal niet iets waar je al te lang bij stil hoeft te staan. Aangezien er al eerder in dit topic over was gesproken dat er bij Mersenne-priemgetallen ontzettend veel rekenwerk komt kijken, kan het in dit specifieke geval nuttig zijn om wat optimalisaties uit te voeren in je rekenwerk. Dat spaart rekenwerk en dus rekentijd. De onderstaande benadering bevat slechts een paar voorbeelden van dergelijke optimalisaties en bij het controleren of een getal een Mersenne-priemgetal is vallen er zeker veel meer (ingewikkelde, op wiskundige regels gebaseerde) optimalisaties uit te voeren. Het is daarom slechts een voorbeeld.

Eerst ga je een paar eenvoudige controles uit te voeren voordat je aan het rekenen slaat.
[list]
• Per definitie is bepaald dat de getallen 0 en 1 geen priemgetal zijn. Niet over nadenken, dat is wat de wiskunde zegt.
• Je weet dat een getal geen priemgetal is als het even is. Een getal dat eindigt op een nul of een vijf is ook geen priemgetal, want dat is deelbaar door 5. Kortom: een getal dat eindigt op 0, 2, 4, 5, 6 of 8 is geen priemgetal.
Even op een rijtje zetten. Stel dat je wilt controleren of het getal 37 een priemgetal is. Het is geen nul of een, dus het kan nog steeds een priemgetal zijn. Het eindigt op een 7, dus dat sluit nog steeds niet uit dat het een priemgetal is. Nu moeten we dus echt aan het rekenen slaan.

Wortel 37 afgerond naar beneden is 6, dus je gaat controleren of het getal deelbaar is door 2, 3, 4, 5 of 6. Is het deelbaar door 2? Nee. Door 3? Ook niet. Door 4, 5 of 6? Nee. Conclusie: het is een priemgetal.

Nu nog iets verder denken. Waarom zou je controleren of het getal deelbaar is door 2? Als het getal deelbaar zou zijn door 2, zou het een even getal zijn. En dat hadden we al vooraf gecontroleerd door te kijken naar het laatste cijfer. We hoeven dus eigenlijk pas te beginnen delen door 3 in plaats van 2: is het getal deelbaar door 3, 4, 5 of 6?

En hoe zit het dan met deelbaar zijn door 4 of 6? Of meer in het algemeen: is het eigenlijk wel nodig om te controleren of het getal deelbaar is door een even getal? Het antwoord is natuurlijk nee. Immers: als het te controleren getal deelbaar is door een even getal, is het te controleren getal ook deelbaar door twee en is het dus geen priemgetal. Als je hebt gecontroleerd of het getal deelbaar is door twee, hoef je daarom niet meer te controleren of het getal deelbaar is door een even getal. Jouw code op regel 24 - for ( int check = 2; check <= nummer; check++) - kun je daarom zo aanpassen dat je begint te controleren bij 3 (in plaats van 2) en je checkt vervolgens of het getal deelbaar is door 5, 7, 9 enzovoort. Dat scheelt je bij grotere getallen pakweg de helft aan rekenwerk, puur omdat je gebruik maakt van wat wiskundige kennis. Dan is die wiskundige kennis toch nog ergens goed voor

[Nick The Heazk]

Sibylle schreef op maandag 25 september 2006 @ 21:29:
Bij welke n treedt de tweede fout dan op volgens jou? dat ga ik eens proberen.

Java:

int n = 2*3*5*7;
int[] array_priem = new int[n];
[... initialise array_priem ...]

for(int i=2; i<=(n/i); i++) {
        if(array_priem[i]!=0) {
            for(int j=2; j<=(n/i); j++){
            array_priem[i*j]=0;
                }
            }
        }

In de eerste itteratie is i = 2, n = 2*3*5*7. De eerste if levert true op en we beginnen de inner lus. j = 2, i = 2, n = 2*3*5*7 en dus n / i = 3*5*7. We doorlopen de inner lus een aantal maal tot we op het punt komen dat j = 3*5*7, i = 2, n = 2*3*5*7. Aangezien j = 3*5*7 <= 3*5*7 wordt de lus nog eenmaal uitgevoerd. We hebben dan dat i*j = 2*3*5*7 == n.

De tweede itteratie is i = 3, n = 2*3*5*7. Weer kunnen we de inner lus betreden met j = 2*5*7 en zo het product i*j = 2*3*5*7 == n maken.

Ik heb de waarde van n geschreven in priemfactoren, omdat enkel bij deze waarden de index-fout optreedt. Deze fout ligt 'm in de integer-division. Voor alle niet-delers van n, is n/i eigenlijk gelijk aan floor(n/i). Bij die waarden zorgt deze afronding ervoor dat je nooit te ver gaat. (Je stopt vlak voor het einde van de array - bij het laatste voorkomen van een veelvoud van i.) Echter bij een gehele deling zonder rest, is er geen afronding en daarom stop je niet net voor het einde van de array.

Mijn inziens kun je de fout corrigeren door (n/i) te vervangen door ceil(n/i) en de "kleiner dan of gelijk aan" te vervangen door een "kleiner dan". Je zorgt ervoor dat bij gehele deling je een itteratie minder doet - tenopzichte van de huidige code - en bij niet-gehele deling moet je je resultaat naar boven aanronden zodanig dat je het aantal itteraties behoudt.

Je kunt ook de integer-deling vervangen door een floating-point-deling en de "kleiner dan of gelijk aan" vervangen door een "kleiner dan".

@Hieronder: Nu zie ik ook waarom hij n+1 als array-lengte gebruikt. Ik dacht dat hij dit deed om die index fout te voorkomen. Het werd me nu pas duidelijk dat Sibylle zijn rij vanaf 0 laat beginnen, niet vanaf 1. (Ik was waarschijnlijk een beetje verward toen ik die eerdere post maakte. Ik had toen gepost vlak nadat ik zelf een meer geoptimaliseerde versie had gescheven (array die enkel oneven getallen bevat met 2 als vast eerste getal.))

[ Voor 10% gewijzigd door Nick The Heazk op 26-09-2006 14:51 ]

[Voutloos]

Nick, die int array wordt door Sibylle aangemaakt met n+1 elementen, niet n. En hij werkt gewoon. Wel zijn er wat optimalisaties mogelijk, zoals Tomatoman en ik al aangaven.

[.oisyn]

[quote]tomatoman schreef op dinsdag 26 september 2006 @ 10:26:
• Je weet dat een getal geen priemgetal is als het even is. Een getal dat eindigt op een nul of een vijf is ook geen priemgetal, want dat is deelbaar door 5. Kortom: een getal dat eindigt op 0, 2, 4, 5, 6 of 8 is geen priemgetal.
Even op een rijtje zetten. Stel dat je wilt controleren of het getal 37 een priemgetal is. Het is geen nul of een, dus het kan nog steeds een priemgetal zijn. Het eindigt op een 7, dus dat sluit nog steeds niet uit dat het een priemgetal is. Nu moeten we dus echt aan het rekenen slaan.

Wortel 37 afgerond naar beneden is 6, dus je gaat controleren of het getal deelbaar is door 2, 3, 4, 5 of 6. Is het deelbaar door 2? Nee. Door 3? Ook niet. Door 4, 5 of 6? Nee. Conclusie: het is een priemgetal.

Nu nog iets verder denken. Waarom zou je controleren of het getal deelbaar is door 2? Als het getal deelbaar zou zijn door 2, zou het een even getal zijn. En dat hadden we al vooraf gecontroleerd door te kijken naar het laatste cijfer. We hoeven dus eigenlijk pas te beginnen delen door 3 in plaats van 2: is het getal deelbaar door 3, 4, 5 of 6?
Beetje nutteloos. Controleren waar het getal op eindigt is handig als je het getal ziet in het decimale stelsel. Dat is iets wat wij mensen gebruiken, niet de PC. Om te kijken of het op een van die getallen eindigt moet je een modulo 10 doen, en dan controleren of de uitkomst 0, 2, 4, 5, 6 of 8 is. Één modulo en 6 checks dus. Kun je net zo goed modulo 2 en modulo 5 checken, scheelt je een hoop potentiele dure branches, en je code wordt er een stuk generieker op. Daarnaast is 10 nogal arbitrair, waarom zou je niet hetzelfde doen voor basis 30 (handiger, omdat je dan ook de 3 kunt skippen) of basis 210 (zodat ook de 7 niet meer hoeft).

Er is maar 1 logische basis om dat mee te doen, en dat is 2, want dat is namelijk de basis die een computer gebruikt. Je wilt dan kijken of het (binair gerepresenteerde) getal eindigt op een 0 of een 1, en dat kan simpelweg door de overige bits eruit te anden: getal & 1.

[Tomatoman]

.oisyn schreef op dinsdag 26 september 2006 @ 13:52:
[...]
Om te kijken of het op een van die getallen eindigt moet je een modulo 10 doen, en dan controleren of de uitkomst 0, 2, 4, 5, 6 of 8 is. Één modulo en 6 checks dus.

Efficiënter is om te controleren of de uitkomst niet 1, 3, 7 of 9 is. Eén modulo en 4 checks dus.

Kun je net zo goed modulo 2 en modulo 5 checken, scheelt je een hoop potentiele dure branches, en je code wordt er een stuk generieker op. Daarnaast is 10 nogal arbitrair, waarom zou je niet hetzelfde doen voor basis 30 (handiger, omdat je dan ook de 3 kunt skippen) of basis 210 (zodat ook de 7 niet meer hoeft).

Dat is waar, zij het dat je dan een nogal lange case statement krijgt. Het ging me niet zozeer om het meest efficiënte algoritme, maar om de algemene conclusie dat je met wat wiskundige basiskennis heel wat rekenwerk kunt besparen.

[soulrider]

tomatoman schreef op dinsdag 26 september 2006 @ 10:26:
Als je hebt gecontroleerd of het getal deelbaar is door twee, hoef je daarom niet meer te controleren of het getal deelbaar is door een even getal. Jouw code op regel 24 - for ( int check = 2; check <= nummer; check++) - kun je daarom zo aanpassen dat je begint te controleren bij 3 (in plaats van 2) en je checkt vervolgens of het getal deelbaar is door 5, 7, 9 enzovoort. Dat scheelt je bij grotere getallen pakweg de helft aan rekenwerk, puur omdat je gebruik maakt van wat wiskundige kennis. Dan is die wiskundige kennis toch nog ergens goed voor

je moet enkel controleren of het deelbaar is door alle reeds bekende priemgetallen die kleiner of gelijk zijn aan de wortel van het te testen getal.
is de modulo 0 is ie deelbaar, is iedoor geen enkele van die priems deelbaar dan is ie ook priem.

waarom controleren of het deelbaar is door 9 als je weet dat het dan ook automatisch deelbaar is door 3 (9 = 3x3) zo ook met 15 (deelbaar door 3 en 5) ?

scheelt je nog iets meer in tijd - kost je mss wel iets meer qua geheugengebruik.

maar om dan bv tot 1.000.000 alle priemgetallen te zoeken moet je enkel de primgetallen kleiner dan 1000 onthouden ;-)

[ Voor 3% gewijzigd door soulrider op 26-09-2006 21:41 ]

[MrBucket]

@soulrider:
Je hebt nu de zgn. "Zeef van Eratosthenes" omschreven (maar dat wist je misschien al).