Controle van een kwadraat, zonder deze te berekenen?

[JWvdVeer]

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.

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

\(2^31\)

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: Selecteer alles

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;

}

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

[ZVdP]

De hoeveelheid priemgetallen kleiner dan 2^31 is 4.9%, bijna 1 op 20. Toch ook meer dan ik op eerste zicht verwacht had.

[kee]

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.

[dragonitor]

ik zou gewoon 2 en 5 pakken,

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

[JWvdVeer]

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

Wat bedoelde je nog meer als ik vragen mag?

De hoeveelheid priemgetallen kleiner dan 2^31 is 4.9%, bijna 1 op 20. Toch ook meer dan ik op eerste zicht verwacht had

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 (

\(\frac{1}{3}-x = \frac{1}{20} \longrightarrow \frac{20}{60} - \frac{3}{60} = \frac{17}{60} = x\)

).

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

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

Heb je binair jammer genoeg bijzonder weinig aan... .

[kee]

Wat bedoelde je nog meer als ik vragen mag?

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.

[ZVdP]

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

Prime counting function

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)

[JWvdVeer]

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

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.

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

Ik weet niet of dat nou zo veel goedkoper is dan dan gewoon met de voorwaarde

\(6n\pm1\)

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

\(\frac{2}{6} = \frac{1}{3}\)

.

In jouw geval streep je alle even getallen af (

\(-\frac{1}{2}\)

).

Daarna alle drievouden, die niet meer even zijn

\(-(\frac{1}{2} \frac{1}{3}) = -\frac{1}{6}\)

.

Vervolgens alle vijfvouden die niet even of drievoud zijn

\(-(\frac{1}{3} \frac{1}{5}) = -\frac{1}{15}\)

.

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

\(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}\)

Dit is net iets beter dan

\(\frac{1}{3}\)

, 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

\(6n\pm1\)

gaat dat nog relatief eenvoudig:

Code: Selecteer alles

	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");

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

[kee]

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.

[kee]

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.

[JWvdVeer]

Ik zal er vanmiddag eens naar kijken .

[kee]

Ik zal er vanmiddag eens naar kijken .

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