Project Euler: priemgetallen

Er zijn een aantal problemen in Project Euler waarin priemgetallen een rol spelen. Soms moet je ze genereren, of je moet een getal zien te controleren dat buiten de grenzen van je datatypes valt. Hoe dan ook, er is een raakvlak met priemgetallen. Ongeacht welk probleem, om tot de oplossing te komen is het handig als je priemgetallen en onderwerpen die ermee te maken hebben beter begrijpt.

Inhoudsopgave

• Deelbaarheidsregels toepassen
• Tot de wortel van een getal rekenen
• Kleine gemeenschappelijke veelvouden gebruiken
• Een getal in priemfactoren ontbinden

Deelbaarheidsregels toepassen

Stel: je bent aan het programmeren en je beseft dat je een functie nodig hebt om te controleren of een getal priem is. Een van de manieren om te onderzoeken of een getal niet priem is, is nagaan of een getal een veelvoud is van (en dus deelbaar is door) andere getallen en dat veelvoud vervolgens te negeren. Deze methode wordt ook wel de zeef van Eratosthenes genoemd en kan in combinatie met andere methodes gebruikt worden.

Je zou dus de algemene deelbaarheidsregels kunnen programmeren, waarbij je ervoor zorgt dat het getal waardoor je deelt groter is dan één en de eerste keer dat het voorbij komt in je functie als priemgetal wordt aangemerkt. Vervolgens kun je voor jouw gewenste getal al deze regels laten doorlopen.

Door eerst naar de deelbaarheidsregels zelf te kijken, verkrijg je meer inzicht in hoe getallen 'werken'.

Deelbaar door 2 – Elk getal dat eindigt op 2, 4, 6, 8, of 0 is even en kan dus niet priem zijn.

Deelbaar door 3 – Tel herhaaldelijk alle cijfers in een getal bij elkaar op en kijk of dat een veelvoud is van 3. Waarom werkt dit? Kijk verder dan 'slechts optellen' en probeer de logica erachter te begrijpen, want ongeveer hetzelfde principe geldt ook voor het getal 9.

Voorbeeld:
Is 12633 deelbaar door 3?
12633 kan ook geschreven worden als (10000 x 3) + (2000 x 3) + (600 x 3) + (30 x 3) + (1 x 3).
Door telkens elk cijfer van het getal af te trekken in de betreffende factor die met drie wordt vermenigvuldigt, creëren we een aparte optelling. De vergelijking moet in evenwicht blijven, dus voegen we de afgetrokken cijfers aan het einde weer toe:
((10000 x 3) – (1 x 3)) +
((2000 x 3) – ( 2 x 3)) +
((600 x 3) – (6 x 3)) +
((30 x 3) – (3 x 3)) +
((1 x 3) – (1 x 3)) = (9999 x 3) + (1998 x 3) + (594 x 3) + (27 x 3) + (0 x 3) + 1 + 2 + 6 + 3 + 3.

Alles wat tussen haakjes staat is een geheel veelvoud van drie geworden en kunnen we vanaf dit punt buiten beschouwing laten. Nu hoeven we alleen nog '1+2+6+3+3' te controleren. De uitkomst is 15 en 1 + 5 is 6; 6 is een veelvoud van 3 en daarmee komen uiteindelijk tot de conclusie dat 12633 ook deelbaar door is 3.

Deelbaar door 4 – Elk getal waarvan de laatste twee cijfers deelbaar zijn door 4.

Deelbaar door 5 – Elk getal dat eindigt op 5 of 0.

Deelbaar door 7 – Verdubbel het laatste cijfer in het getal, trek het af van het gehele getal. Herhaal deze stap zo vaak als nodig is. Controleer of de uitkomst gelijk is aan 7.

Voorbeeld:
Is 183 deelbaar door 7?
3 x 2 = 6
183 – 6 = 177
7 x 2 = 14
177 – 14 = 163
3 x 2 = 6
163 – 6 = 157
…

Na de laatste berekeningen houd je het getal 3 over. Dat is geen veelvoud van 7, dus 183 is niet deelbaar door 7.

Deelbaar door 9 – Voor 9 geldt exact hetzelfde als voor 3, tel alle cijfers van het getal bij elkaar op. Als het antwoord een veelvoud is van 9, is het getal zelf deelbaar door 9.

Deelbaar door 10 – Elk getal dat eindigt op 0, of als het getal deelbaar is door zowel 2 en 5.

Deelbaar door getallen groter dan 10 – Deze regel gaat niet altijd op, maar geldt wel voor getallen zoals 6, 8, 12, 14, 15, 16, enzovoort. Voorbeeld: 2 x 3 = 6, dus gebruik je de deelbaarheidsregels van 2 en 3. Een getal is deelbaar door 15 als het deelbaar is door 3 en 5, want 3 x 5 = 15.

Tot de wortel van een getal rekenen

Wat als je al een functie hebt die controleert of het nummer dat je invoert een priemgetal is? Werkt dat ook nog als je een zeer groot getal zou willen berekenen in plaats van een getal onder de honderd?

Voorbeeldgetal om te testen: 126

Mogelijkheid 1 – tot en met het maximum zoeken
Stel dat je zou blijven zoeken van 1 tot en met 126 (126 is het maximum). Dan kom je uiteindelijk op het volgende: 1 x 126 = 2 x 63 = 3 x 42 = 7 x 18 = 9 x 14 =126. De factoren zijn dus 1, 2, 3, 7, 9, 14, 18, 42, 63 en 126. Als je daarvan vervolgens de priemgetallen zoekt, kom je uit op 2, 3 en 7.

Mogelijkheid 2 – tot en met de wortel van het maximum zoeken
Zoek de wortel van 126. 11 x 11 = 121 en 12 x 12 = 144. De wortel van 126 zit duidelijk tussen 11 en 12 in en 144 is groter dan 126, dus kies je 11. Deel 126 door 1 tot en met 11 en kijk welke factoren eruit komen zonder rest na deling. Zoek nu in de factoren de priemgetallen. Je komt ongetwijfeld opnieuw uit op 2, 3 en 7.

In beide gevallen heb je nu meer dan twee factoren gevonden, waardoor je kunt concluderen dat 126 geen priemgetal is. Alles wat groter is dan de wortel van 126 kun je dus negeren. Door deze mogelijkheid te combineren met de deelbaarheidsregels haal je al meer dan de helft van de zoektijd weg!

Deze kennis is onder andere toepasbaar in Euler probleem 7: 10001st prime, waarin naar een priemgetal wordt gezocht.
Probleem:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?

Aanpak
Een manier om dit op te lossen is een functie te gebruiken die getallen genereert en het te laten stoppen bij het vinden van een priemgetal op plek nummer 10001 in de gevonden reeks priemgetallen. In de functie zelf hoef je dan alleen maar van één tot en met de wortel van elk getal uit te rekenen. Het gaat nog een stap verder in Euler probleem 10: summation of primes, waarin je priemgetallen met een waarde onder de twee miljoen moet optellen.

Kleine gemeenschappelijke veelvouden gebruiken

Laten we eens kijken naar breuken: 1/5 + 2/7. Om deze twee breuken op te tellen, is het makkelijker als je het kgv zoekt.

Veelvouden van 5:
5, 10, 15, 20, 25, 30, 35, 40, 45, 50

Veelvouden van 7:
7, 14, 21, 28, 35, 42, 49, 56, 63, 70

Het eerste gemeenschappelijke en kleinste veelvoud dat je tegenkomt is 35, wat in dit geval gelijk is aan 5 x 7.

1/5 x 7 = 7/35
2/7 x 5 = 10/35
7/35 + 10/35 = 17/35

De uiteindelijke breuk kan in dit geval niet vereenvoudigd worden, want zeventien is een priemgetal en heeft geen gemeenschappelijke deler met vijfendertig.

Deze kennis van het kgv is bijvoorbeeld toepasbaar op Euler probleem 5: smallest multiple
Probleem:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Aanpak
Het getal 2520 kan door de getallen één tot en met tien worden gedeeld zonder rest en is tegelijkertijd het kleinste getal waarbij dit mogelijk is. De rekensom 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 levert echter 3 628 800 op. Je kan de rekensom ook schrijven als een faculteit: !10 betekent precies hetzelfde als de getallen één tot en met tien vermenigvuldigen.

De vraag die je moet zien te beantwoorden is dus: hoe levert !10 het getal 2520 op in plaats van ruim drie miljoen?

Stel dat je faculteit 1 tot en met 20 zou moeten uitrekenen, dat is hetzelfde als 1 x 2 x 3 x … x 18 x 19 x 20. Kortom, een gigantisch groot getal. Door het kgv van de getallen 1 tot en met 20 te vinden, maak je dat getal veel kleiner. Zoek eerst het kgv tussen 1 en 2, vervolgens tussen 2 en 3, dan tussen 3 en 4, en zo tot en met 19 en 20.

Een getal in priemfactoren ontbinden

Soms is het nodig priemfactorisatie toe te passen bij een groter getal. Daarbij deel je een getal uitsluitend door priemgetallen. Door de kennis te gebruiken die je nu hebt opgedaan weet je dat je een functie kunt programmeren die alleen tot aan de wortel van het getal hoeft te lopen, om zo de rekentijd te verminderen. Je deelt het gevraagde getal door het eerstvolgende bestaande priemgetal. Vervolgens deel je de uitkomst door het volgende priemgetal. Je herhaalt deze stap net zolang totdat de uitkomst gelijk is aan één.