[quote]Ik zal er vanmiddag eens naar kijken ;) .[/quote]



Ok, als je dat doet, ik zie dat in de zin "Ik heb verondersteld dat het getal ook gewoon een markering heeft in de rij." de "1" ervan tussenuit gevallen is, dus "Ik heb verondersteld dat het getal 1 ook een markering heeft in de rij, die helemaal vooraan dan."

Ik zal er vanmiddag eens naar kijken ;) .

Ik ken niks van C, maar misschien kan je het hiermee uitwerken voor wat de opslag betreft (dit is een voorbeeld van hoe het idee uit te werken), als je geïnteresseerd bent. Ik heb het gedaan voor het schrappen van de veelvouden van 2,3 en 5.

In je 'rij priemgetallen' van nullen (geen priemgetal) en enen (priemgetal) laat je de veelvouden van 2,3 en 5 vallen (hoe je die 'rij' opstelt ga ik hier nu niet zetten, maar wel hoe je terugvindt of het een priemgetal is, opstellen is dan gelijkaardig wat het idee betreft). Ik heb verondersteld dat het getal ook gewoon een markering heeft in de rij.

De getallen relatief priem met 30 zijn 1,7,11,13,17,19,23 en 29.

Definieer rij={0,1,0,0,0,0,0,2,0,0,0,3,0,4,0,0,0,5,0,6,0,0,0,7,0,0,0,0,0,8}

Zij a het te controleren getal waarvan je wil weten of het als priemgetal in de rij staat.

r=a%30;

q=int(a/30);

Indien rij®=0, dan niet priem.

Anders heb je de markering nodig op volgende index (in de veronderstelling dat de eerste index 1 zou zijn (ik ken niks van C), als die 0 is in C moet je nog 1 aftrekken van het volgende):

index=8*q+rij®;

Zoiets zou het moeten zijn. Best wel controleren of het klopt (fouten zijn heel snel gemaakt op deze manier). Het zou analoog gaan als je de veelvouden van 7,11 of misschien nog meer laat vallen. De rij 'rij' wordt dan wel al snel heel groot.

edit: ® geraakt niet opgelost, het moet een r tussen haakjes zijn, maar dat wordt automatisch vervangen.

Die 8/30 vind je als volgt: (1*2*4)/(2*3*5). Voor 7 wordt dit (1*2*4*6)/(2*3*5*7). Denk aan de Euler-totiënt-functie.

Om te weten of een getal erin staat moet je inderdaad aan het rekenen (zoals ik ook heb aangehaald, dat dat eigenlijk niet de bedoeling is). Je moet een schema opslaan (die 2/4 afwisselend optellen is in feit ook een schema, maar dan tot 6, 1 en 5 (modulowijs een meer en een minder dan 6) zijn namelijk relatief priem met 6, de andere niet, bij 5 erbij bijvoorbeeld breidt je schema tot 30 uit met de getallen relatief priem met 30 (vandaar dat ik het daarnet over de Euler-totiënt-functie had die je het aantal geeft), met 7 erbij tot 210 enzovoort. Dat is wel niet zo ingewikkeld denk ik (als je dat eens rustig bekijkt en nauwkeurig uitwerkt).

Op die manier haalde ik in mijn allereerste post in dit topic al aan dat je om een getal te factoriseren op de naïeve manier wel de methode (afwisselend 2 en 4 overlaten in je getallen waarmee je 'controleert' en controleren tot je besluit dat het geen priemgetal is of anders tot de wortel van je getal waarvan je nagaat of het een priemgetal is) ook kan uitbreiden tot de veelvouden van 5, 7 en eventueel 11, die je ook niet controleert. Opnieuw met zo'n schemaatje (tot 2*3*5*7 en eventueel *11 erbij) op te stellen en dan bloksgewijs steeds bij te tellen om de getallen te vinden waarmee je moet controleren.

	unsigned int iTeOnderzoekenGetal = 74917; // 6 * 12486 + 1, dus positie 12486 * 2 + 1 = 24973

unsigned char iDelingRest = ((iTeOnderzoekenGetal + 1) % 6);

printf("%u\r\n", iDelingRest);

if(!iDelingRest || (iDelingRest == 2)){

unsigned iPositie = ((((iTeOnderzoekenGetal + 1) / 6) << 0x1) + (iDelingRest >> 0x1));

  printf((primeTable[iPositie / 8] & (1 << (iPositie & 0x7)))? "Priemgetal!\r\n" : "Geen priemgetal\r\n");

} else printf("Geen priemgetal!\r\n");

[quote](ik heb blijkbaar wel de verkeerde link geplaats met 2^32 ipv 2^31)[/quote]Boeit niet, had het direct door toen ik zag dat het antwoord hier op de site niet klopte met het antwoord wat in Wolfram stond. Met 31 ipv 32 klopte het wel ;) .

Wist niet dat daar overigens een functie voor bestond.

[quote]Het zou nog ingewikkelder maar 'goedkoper' zijn als je tot op zekere hoogte anders zou werken, want al die veelvouden van 2 moeten er niet in, da's de helft gespaard, dat priemgetal houd je wel apart bij, maar die van 3 ook niet, en die van 5 en waar stopt het dan, want dan moet je tóch alweer beginnen rekenen voor je weet of een getal priem is en voor je een lijst beschikbaar hebt in de gewenste vorm, en dat was net niet de bedoeling...[/quote]

Ik weet niet of dat nou zo veel goedkoper is dan dan gewoon met de voorwaarde [tex]6n\pm1[/tex] werken. Ofwel, dat je begint met het getal 5 (n=1) en vervolgens afwisselend twee en vier optellen. Van elke zes getallen doe je er dan 2, ofwel [tex]\frac{2}{6} = \frac{1}{3}[/tex].

In jouw geval streep je alle even getallen af ([tex]-\frac{1}{2}[/tex]).

Daarna alle drievouden, die niet meer even zijn [tex]-(\frac{1}{2} \frac{1}{3}) = -\frac{1}{6}[/tex].

Vervolgens alle vijfvouden die niet even of drievoud zijn [tex]-(\frac{1}{3} \frac{1}{5}) = -\frac{1}{15}[/tex].

Kortom, je doet steeds drie vergelijkingen om uiteindelijk uit te komen op een aantal getallen van:

[tex]1 -\frac{1}{2} - \frac{1}{6} - \frac{1}{15} = \frac{30}{30} - \frac{15}{30} - \frac{5}{30} - \frac{2}{30} = \frac{30}{30} - \frac{22}{30} = \frac{8}{30}[/tex]

Dit is net iets beter dan [tex]\frac{1}{3}[/tex], namelijk 20% minder opslagruimte.

Het nadeel is echter dat met deze methode hondsmoeilijk is om te bepalen of een getal ergens in de rij staat, en zo ja: waar?

Bij de [tex]6n\pm1[/tex] gaat dat nog relatief eenvoudig:

[code] unsigned int iTeOnderzoekenGetal = 74917; // 6 * 12486 + 1, dus positie 12486 * 2 + 1 = 24973

unsigned char iDelingRest = ((iTeOnderzoekenGetal + 1) % 6);

printf("%u\r\n", iDelingRest);

if(!iDelingRest || (iDelingRest == 2)){

unsigned iPositie = ((((iTeOnderzoekenGetal + 1) / 6) << 0x1) + (iDelingRest >> 0x1));

printf((primeTable[iPositie / 8] & (1 << (iPositie & 0x7)))? "Priemgetal!\r\n" : "Geen priemgetal\r\n");

} else printf("Geen priemgetal!\r\n");[/code]

Maar hoe ik dat voor jouw methode zou moeten doen (en hoeveel bewerkingen daar voor plaats moeten vinden) weet ik niet ;) .

[quote]Hoe kwam je eigenlijk aan die formule die je in Wolfram hebt gestopt?[/quote]



[url=http://en.wikipedia.org/wiki/Prime_counting_function]Prime counting function[/url]

Ik zag dat die met pi genoteerd werd en probeerde maar eens.

(ik heb blijkbaar wel de verkeerde link geplaats met 2^32 ipv 2^31)

[quote]Wat bedoelde je nog meer als ik vragen mag?[/quote]

De post was gelinkt aan die ervoor van mij ter verdediging van de zeef van Eratosthenes (waar ik verkeerd begrepen was) om alles in 1 keer te berekenen.

[quote]Met die post bedoelde ik wel nog heel wat meer, maar dat kan inderdaad ook zo gebruikt worden gewoon als opslag.[/quote]Wat bedoelde je nog meer als ik vragen mag?

[quote]De hoeveelheid priemgetallen kleiner dan 2^31 is 4.9%, bijna 1 op 20. Toch ook meer dan ik op eerste zicht verwacht had[/quote]Inderdaad, dat vind ik ook nog redelijk veel. Gezien we 2 op de 6 getallen afgaan. Moeten we alsnog 17 op de 60 kandidaten afstrepen ([tex]\frac{1}{3}-x = \frac{1}{20} \longrightarrow \frac{20}{60} - \frac{3}{60} = \frac{17}{60} = x[/tex]).

Hoe kwam je eigenlijk aan die formule die je in Wolfram hebt gestopt?

[quote]dan kunnen alleen de getallen die eindigen op 1 3 7 9 priemgetallen zijn[/quote]Heb je binair jammer genoeg bijzonder weinig aan... ;) .

ik zou gewoon 2 en 5 pakken,

dan kunnen alleen de getallen die eindigen op 1 3 7 9 priemgetallen zijn

Met die post bedoelde ik wel nog heel wat meer, maar dat kan inderdaad ook zo gebruikt worden gewoon als opslag.

Het zou nog ingewikkelder maar 'goedkoper' zijn als je tot op zekere hoogte anders zou werken, want al die veelvouden van 2 moeten er niet in, da's de helft gespaard, dat priemgetal houd je wel apart bij, maar die van 3 ook niet, en die van 5 en waar stopt het dan, want dan moet je tóch alweer beginnen rekenen voor je weet of een getal priem is en voor je een lijst beschikbaar hebt in de gewenste vorm, en dat was net niet de bedoeling... Het hangt allemaal van de bedoeling af en waarvoor je het nodig hebt.

De hoeveelheid priemgetallen kleiner dan 2^31 is [url=http://www.wolframalpha.com/input/?i=pi%282%5E32%29%2F2%5E32]4.9%[/url], bijna 1 op 20. Toch ook meer dan ik op eerste zicht verwacht had.

int main(){

unsigned int maxPrime = 1 << 31; // 2^31

unsigned char *primeTable = malloc((maxPrime / 8) * sizeof(char));

if(primeTable == NULL) return 1;

// Invoegen gaat dan zo:

unsigned int priemGetal =  99989;

primeTable[priemGetal / 8] |= 1 << (priemGetal % 8); // Zet het bit wat het nummer voorstelt op 1.

// Uitlezen gaat dan zo:

unsigned int priemGetal =  99989;

int isPriem = primeTable[priemGetal / 8] &= 1 << (priemGetal % 8);

printf(isPriem? "%u is een priemgetal" : "%u is geen priemgetal", priemGetal);

return 0;

}

[quote]Toch nog een extra toevoeging (ik blijf er maar mee bezig ;) ): wat memory betreft kan je 8 "getallen" PER BYTE opslaan, omdat je enkel 1 of 0 zou moeten markeren als je alles in 1 keer doet (of in blokken), maar ik begrijp ook dat dat allemaal wellicht niet te implementeren valt.[/quote]Inderdaad, daaraan heb je gelijk dat het mogelijk is. Maar ik vraag me af of dat uiteindelijk geheugentechnisch beter is. Ik betwijfel het dat één op de 32 natuurlijke getallen tot [tex]2^31[/tex] een priemgetal is. Vanaf dat moment is jou oplossing geheugentechnisch goedkoper. En zelfs ook uitvoerbaar. Het betreft dan overigens alsnog altijd 256MB die je er in investeert. Al zou het kunnen dat deze oplossing goedkoper is en zelfs implementeerbaar.

Bijv. zo:

[code]int main(){

unsigned int maxPrime = 1 << 31; // 2^31

unsigned char *primeTable = malloc((maxPrime / 8) * sizeof(char));

if(primeTable == NULL) return 1;

// Invoegen gaat dan zo:

unsigned int priemGetal = 99989;

primeTable[priemGetal / 8] |= 1 << (priemGetal % 8); // Zet het bit wat het nummer voorstelt op 1.

// Uitlezen gaat dan zo:

unsigned int priemGetal = 99989;

int isPriem = primeTable[priemGetal / 8] &= 1 << (priemGetal % 8);

printf(isPriem? "%u is een priemgetal" : "%u is geen priemgetal", priemGetal);

return 0;

}[/code]

Al denk ik dat het invullen van de tabel alsnog het snelste gaat door middel van mijn methode.

Toch nog een extra toevoeging (ik blijf er maar mee bezig ;) ): wat memory betreft kan je 8 "getallen" PER BYTE opslaan, omdat je enkel 1 of 0 zou moeten markeren als je alles in 1 keer doet (of in blokken) (je zet eerst alles 1 of zo en maakt de plaats 0 als je moet markeren), maar ik begrijp ook dat dat allemaal wellicht niet te implementeren valt.

Ja zo is het zeker niet voordeliger. Maar het is zo wel duidelijk dat het dan niet uitmaakt of je die in die of een andere volgorde wegschrapt op die manier. Dat was niet wat ik bedoelde. Het punt was dat het "checken" nogal eenvoudig wordt als je die allemaal laat staan, omdat je niets moet delen, want degene die eruitvallen staan op regelmatige afstanden van elkaar. Je moet enkel iets erbij tellen en dan op een of andere manier "markeren". Maar op die manier is het wellicht moeilijk praktisch te implementeren. En dan moet je nog meer "checken (markeren)", want je gaat veel getallen een heel aantal keer markeren, hoewel je met getaltheorie erbij te sleuren dat misschien wel zou kunnen vermijden als je dat eens bekijkt.

Een combinatie zou dan wel ook kunnen, bijvoorbeeld per blok van 10000 de zeef toepassen waarbij je 1 deling per controle moet toepassen om de rest te bepalen van het eerste getal van het blok bij die deling door dat controlegetal, terwijl de rest dan gewoon sprongen maken is. Maar het hangt ervan af of zoiets efficiënt geprogrammeerd kan worden in C denk ik. Als je een basisprogrammeertaal zou hebben (dichter bij de machinetaal) zou je het zo wel veel efficiënter kunnen programmeren denk ik. Nu is het wellicht niet mogelijk.

[quote]Voordeliger qua rekentijd is het wel volgens mij (je hoeft eigenlijk geen enkele deling uit te voeren en alleen maar te schrappen met regelmatige tussenpozen). Memory-consuming is waar, maar echt onmogelijk? Je wil toch ook alle priemgetallen opslaan?[/quote]Nee, het is zeker niet voordeliger qua rekentijd. Dat kan ik je vrij eenvoudig uitleggen.

Stel dat we de lijst: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 hebben.

Dan streep je eerst af (2):

2, 4, 6, 8, 10, 12, 14, 16, 18, 20 (hiervoor check je in totaal 18 getallen, je streept er 9 weg, houdt er 11 over).

Daarna streep je af (3):

9 (hiervoor check je in totaal 7 getallen, je streept er 1 weg, je houdt er 10 over).

Daarna streep je af (5):

15 (hiervoor check je in totaal 6 getallen).

Voor de overige getallen moet je nog 10x checken en streep je niets weg.

In totaal check je dan 18 + 7 + 6 + 10 = 41 getallen (met modulo, ofwel delingsrest). En schrap je er in totaal 9 + 1 + 1 = 11 (dat houdt dus ook in dat je 11x een geheugenblok moet gaan verplaatsen, omdat een getal gewist moet worden).

Uiteindelijk houdt je over:

1, 2, 3, 5, 7, 11, 13, 17, 19

In mijn geval, heb je eerst de voorwaarde (nu nog maar één). Ofwel, we beginnen de lijst met de getallen:

1, 2, 3, 5, 7, 11, 13, 17, 19 (sorry, maar per ongeluk allemaal priemgetallen. Maakt in feite niet zo veel uit).

Voor deze lijst worden er per getal twee berekeningen gedaan: 9x2 = 18 berekeningen.

Voor deze lijst worden er: 6 + 5 + 4 + 3 + 2+ 1 = 21 vergelijkingen gedaan.

Voor deze lijst worden er geen memoryblokken gekopiëerd en verplaatst, omdat de getallen pas toegevoegd worden na controle.

[quote]Memory-consuming is waar, maar echt onmogelijk? Je wil toch ook alle priemgetallen opslaan?[/quote]Niet echt onmogelijk. Maar een beetje irrealistisch om de getallen 1 - 2^31 op te slaan. Dat zou namelijk:

[tex]2^{31} \cdot 4 bytes = 8.6 \cdot 10^9 bytes = 8GB[/tex] kosten van het werkgeheugen (een getal kost vier bytes, op 64-bits machines soms 8 bytes). Dat is iets wat jij wss. ook niet in jouw kast hebt zitten en anders zeker niet overhebt voor enkel een afstreeplijst van priemgetallen.

Daarnaast kost een dergelijke lijst opstellen ook eerst heel veel rekentijd. Je moet namelijk eerst van 1 - 2^32-1 tellen. En daarna nog 2^32-1 + 2^32-2 + 2^31 ... om elke keer af te strepen.

Als je overigens ook op Wikipedia kijkt, zie je dat dit vooral een goede methode is voor snel de kleine priemgetallen te berekenen. Dat is dus ook wat ik min of meer denk dat het geval is. Al met al zou ik deze methode niet aanraden.

Maar sowieso bedankt voor het meedenken ;) .