Een week geleden was ik bezig met een toepassing waarbij ik getallen moest ontbinden in priem-factoren, en vroeg ik me ook af of er een algoritme kan gevonden worden dat eenvoudigweg een lijst produceert met alle priemgetallen tot en met een (geheel) getal N >= 5
Wel, dezelfde dag vond ik al een methode:
Ziehier mijn methode voor de automatische berekening van priemgetallen, tot en met een (geheel) getal N >= 5 :
i) Bereken n = (N+1)/6, en rondt af naar het hoger gelegen geheel getal.
ii) Alle priemgetallen voldoen aan dit algoritme:
Voor alle i = 1 tot en met n = (N+1)/6, vindt men als volgt de 'kandidaat-priemgetallen' k1(i) en k2(i) (alle priemgetallen voldoen hieraan, maar nadien zullen we nog een aantal getallen, die géén priemgetallen zijn, uit deze lijst moeten schrappen) :
k1(i) = (i * 6) - 1
k2(i) = (i * 6) + 1
Zo vinden we, voor i = 1, het paar 5 en 7. Voor i = 2 vinden we 11 en 13. Voor i = 3 vinden we 17 en 19, en voor i = 4 vinden we de getallen 23 en 25. Dit laatste getal is echter geen priemgetal (25 = 5*5), maar dat is geen probleem, immers, het hogere algoritme levert ons slechts 'kandidaat-priemgetallen', maar uit deze lijst moeten we nadien nog een aantal getallen schrappen, en dit volgens een methode die hieronder verder beschreven wordt, en die wel erg efficiënt is.
Voor i = 5 vinden we 29 en 31; voor i = 6 : 35 (= 5*7, eveneens geen priemgetal, maar zal nadien uit deze lijst van 'kandidaat-priemgetallen' geschrapt worden) en 37; voor i= 7 : 41 en 43, en voor i = 8 vinden we 47 en 49 (= 7*7, geen priemgetal, maar zal later geschrapt worden). Enz, enz... Wie, met behulp van dit zeer eenvoudige algoritme ( (i*6)+/- 1), een volledige lijst maakt, zal zien dat deze lijst alle priemgetallen levert, plus een aantal getallen, die geen priemgetallen zijn, en die we nadien nog zullen moeten schrappen uit deze lijst.
Maar wie nauwkeurig genoeg kijkt, zal zien dat de getallen die zelf géén priemgetallen zijn, en die later dus nog moeten worden geschrapt uit deze lijst, zelf veelvouden of machten zijn van (priem)getallen uit deze lijst. De getallen die geen priemgetallen zijn, en die nog moeten worden geschrapt uit deze lijst, voldoen dus zelf wél aan een algoritme: namelijk dat het veelvouden en/of machten zijn van getallen uit deze lijst. We kunnen deze extra getallen dus eenvoudig elimineren met behulp van een wiskundige methode (zie verder).
Maar eerst even recapituleren: Met behulp van het eenvoudige algoritme ((i*6)+/- 1) bekomen we een lijst van paren (k1(i) en k2(i)) van 'kandidaat-priemgetallen', die maximaal bestaat uit (N+1)/3 getallen. De oorspronkelijke reeks van N gehele getallen wordt op die manier dus al gereduceerd tot ongeveer één derde van het totaal aantal getallen. (Er schieten dus nog maar (N+1)/3 getallen over, die voorkomen in paren (k1(i) en k2(i)) van 'kandidaat-priemgetallen').
Maar hieruit moeten we nog een aantal getallen schrappen:
De lijst van 'Kandidaat-Priemgetallen' rangschikken we eerst in een Vector 'VKP', bestaande uit (N+1)/3 gehele getallen, waarin deze paren k1(i) en k2(i) als volgt voorkomen:
VKP = [k1(i=1) k2(i=1) ... k1(i) k2(i) ... k1(i=(N+1)/6) k2(i=(N+1)/6)]
(met i = 1 tot en met (N+1)/6; (N+1)/6 paren, van in totaal (N+1)/3 getallen!)
(Dit is dus een vector met (N+1)/3 getallen)
De getallen die we (uit deze Vector 'VKP' van 'Kandidaat-Priemgetallen') moeten schrappen, vinden we uit het product van een matrix 'M1', met een tweede matrix 'M2'. Beide matrices 'M1' en 'M2' worden gevormd op basis van deze Vector 'VKP' van 'Kandidaat-Priemgetallen'!
TSKP = M1 * M2
De eerste Matrix 'M1' moeten we als volgt opbouwen (uit de reeds gevonden Vector 'VKP' van 'Kandidaat-Priemgetallen') :
M1 =
(* De eerste kolom van deze matrix 'M1', wordt gevormd door dezelfde getallen te nemen uit de Vector 'VKP' (van 'Kandidaat-Priemgetallen') en de andere kolommen worden opgevuld met nullen: )
(** Op die manier krijgen we dus een matrix 'M1', die bestaat uit (N+1)/3 rijen, en (N+1)/3 kolommen : )
(*** En de eerste kolom van deze matrix 'M1' is dus gelijk aan de vector 'VKP' : )
k1(i=1) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
k2(i=1) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
k1(i=2) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
k2(i=2) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
... ... ... ... ...
k1(i) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
k2(i) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
... ... ... ... ...
k1((N+1)/6) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
k2((N+1)/6) 0 ... ... 0 (* vanaf de tweede kolom alleen nullen)
De tweede Matrix 'M2' moeten we als volgt opbouwen (uit de reeds gevonden Vector 'VKP' van 'Kandidaat-Priemgetallen') :
M2 =
(* De eerste rij van deze matrix 'M2', wordt gevormd door dezelfde getallen te nemen uit de Vector 'VKP' van 'Kandidaat-Priemgetallen'. De eerste rij is dus gelijk aan de Vector 'VKP' van 'Kandidaat-Priemgetallen' ;-)
(** Idem voor de andere rijen, die allemaal een herhaling zijn van deze Vector 'VKP' van 'Kandidaat-Priemgetallen' ;-)
(*** Op die manier krijgen we dus een matrix 'M2', die bestaat uit (N+1)/3 rijen, en (N+1)/3 kolommen, en waarvan alle rijen gelijk zijn aan de Vector 'VKP' van 'Kandidaat-Priemgetallen' : )
k1(i=1) k2(i=1) .... k1(i) k2(i) .... k1(i=(N+1)/6) k2(i=(N+1)/6)
k1(i=1) k2(i=1) .... k1(i) k2(i) .... k1(i=(N+1)/6) k2(i=(N+1)/6)
.... .... .... .... .... .... .... ....
.... .... .... .... .... .... .... ....
k1(i=1) k2(i=1) .... k1(i) k2(i) .... k1(i=(N+1)/6) k2(i=(N+1)/6)
k1(i=1) k2(i=1) .... k1(i) k2(i) .... k1(i=(N+1)/6) k2(i=(N+1)/6)
En daarna moeten we de matrix 'M1' enkel nog vermenigvuldigen met de matrix 'M2', en dan krijgen we een nieuwe matrix TSKP, met 'Te Schrappen Kandidaat-Priemgetallen':
TSKP = M1*M2
Bemerk dan dat alle elementen op de diagonaal (van links-boven naar rechts-onder) de kwadraten zijn van de originele 'Kandidaat-Priemgetallen' (afkomstig uit de Vector 'VKP' van 'Kandidaat-Priemgetallen'), en dat de matrix TSKP bovendien symmetrisch is t.o.v. die diagonaal (alle producten van 'Kandidaat-Priemgetallen' met elkaar, komen dus dubbel voor, zowel boven als onder die diagonaal), en daarom mogen we daarna, in deze matrix TSKP, alle getallen onder de diagonaal schrappen (of vervangen door nullen), en zo bekomen we dan een nieuwe matrix TSKP' (van 'Te Schrappen Kandidaat-Priemgetallen'), waarbij:
TSKP' =
k1(1)*k1(1) k1(1)*k2(1) .... .... k1(1)*k1((N+1)/6) k1(1)*k2((N+1)/6)
0 k2(1)*k2(1) .... .... k2(1)*k1((N+1)/6) k2(1)*k2((N+1)/6)
0 0 k1(2)*k1(2) .... k1(2)*k1((N+1)/6) k1(2)*k2((N+1)/6)
0 0 0 k2(2)*k2(2) ...... k2(2)*k2((N+1)/6)
..... ...... ...... ...... ...... ......
..... ...... ...... ...... ...... ......
0 0 ..... ..... k1(i)*k1((N+1)/6) k1(i)*k2((N+1)/6)
0 0 ..... ..... k2(i)*k1((N+1)/6) k2(i)*k2((N+1)/6)
..... ...... ...... ...... ...... ......
..... ...... ...... ...... ...... ......
0 0 ...... ...... ...... k1((N+1)/6)*k2((N+1)/6)
0 0 ...... ...... 0 k2((N+1)/6)*k2((N+1)/6)
En aangezien de opdracht erin bestond om de priemgetallen te geven tot en met een geheel getal N, mogen we alle producten (van 'kandidaat-priemgetallen') die groter zijn dan N, uit hogere matrix TSKP' schrappen (of vervangen door nul). In praktijk zijn dat heel wat getallen, immers, de waarde van die producten loopt snel op!
En ter volledigheid moet ik ook vermelden dat hogere methode enkel de priemgetallen geeft vanaf het getal 5. (5 en 7 vormen het eerste paar, dat gevonden wordt bij de waarde i = 1 ;-) (Bij i = 2 krijgen we 11 en 13 als volgende paar; en bij i = 3 krijgen we 17 en 19, maar let op, want vanaf i = 4 krijgen we het paar (van 'kandidaat-priemgetallen) 23 en 25, maar 25 wordt nadien geschrapt, immers, het getal 25 (= 5*5) is het eerste getal (op rij 1 en kolom 1) van de matrix TSKP' met Te Schrappen Kandidaat-Priemgetallen ;-). En ja, natuurlijk weet ik ook wel dat alle getallen die eindigen op 5 (veelvouden van 5) sowieso mogen geschrapt worden, maar toch geeft mijn methode ook andere getallen (zoals 49, 77, 91, 119, 121, 133, 143, 161, 169, 187, ... enz, enz) in de matrix TSKP' die uit de originele Vector VKP (van Kandidaat-Priemgetallen) moeten geschrapt worden. (De eerste rij van de matrix TSKP' wordt wel gevormd door welbepaalde veelvouden van 5 (te weten: 25, 35, 55, 65, 85, 95, ... enz; niet alle, immers, veelvouden van 5, die ook veelvouden van 2 en/of 3 zijn (zoals bijvoorbeeld het getal 15 en het getal 30, enz...), komen niet eens voor in de Vector VKP (van Kandidaat-Priemgetallen), en moeten daarom nadien ook niet meer geschrapt worden, en dus komen ze ook niet meer voor in de eerste rij van de matrix TSKP' ;-) (Wat dat betreft is mijn methode wel erg efficient, want er wordt alleen gerekend met 1/3 van de getallen die er nog toe doen! Maar akkoord, veelvouden van 5, en dus getallen die eindigen op '0' (door het gebruikte algoritme (i*6 +/- 1) komen even getallen evenwel niet meer voor in VKP (en ook niet in TSKP', dus dat is geen probleem) of '5', mocht men sowieso schrappen.)
Maar aan mijn lijst van priemgetallen (te beginnen met 5), moet men achteraf dus wel nog de getallen 2 en 3 toevoegen (Opm: het getal 1 wordt niet meer gerekend als priemgetal, maar in mijn tijd was dat nog wél het geval ;-)
Ir. Daniel De Caluwé
