“Welke manier is het best voor onze priemgetallenloterij?” vroeg zoon. Ik was even verrast, en zoon toonde het volgende papiertje. “We hebben een priemgetallen loterij bedacht! We verkopen 100 loten voor 10 euro, maar we vroegen ons alleen nog af met welke twee manieren we het meeste geld voor het goede doel kunnen verdienen!”
Ik staar naar het papier en vraag om uitleg.
“We verkopen 100 loten en hebben dan duizend euro. We hebben twee manieren van uitbetalen bedacht. Bij de eerste manier krijg je een lootje met een getal (1 tot 100) en dat getal kun je ontbinden in factoren.
- Heeft je lot drie of minder factoren dan geen prijs 12=2 x 2 x 3 is niks
- 4 factoren: geld terug (10 euro)
- 5 factoren: 25 euro!
- 6 of meer: hoofdprijs van 100 euro
“Oh, zijn er getallen onder de 100 met 6 factoren dan?”
“Ja,” zegt zoon. “64. Kan je heel vaak delen door twee!”
“Oh ja. 64 = eh, 2 x 2, x2 x2 x 2, x2. Da’s de hoofdprijs zie ik? En de andere manier?”
“We hebben ook nog een andere bedacht namelijk gewoon dat je lootje een getal heeft en als dat een priemgetal is, betalen we het bedrag uit wat op het lot staat.”
“Nou geef mij dan maar 97, alsjeblieft.”
“He wat?”
“Ik denk dat dat een priemgetal is, ja toch?”
“Zevenennegentig? Ja dat zou kunnen. Maar we weten niet bij welke van deze twee manieren we het meeste prijzengeld moeten uitgeven”
“Daar is vast wel een programmaatje voor te maken, om dat uit te rekenen.”
“Ok, maak het even.”
Ik had beter niets kunnen zeggen. Eerst maar even doorvragen.
“Die factoren he? En die priemgetallen. Hoe bepaal je eigenlijk hoeveel factoren een getal heeft? Ik bedoel, als ik 24 heb, dan weet ik dat ik het door twee kan delen. Da’s al 1 factor, maar daarna?”
“Dan probeer je het eerst nog een keer, voordat je naar het volgende priemgetal gaat.”
Zoon heeft er al over nagedacht, merk ik.
“Ok, dus ik heb 24 / 2 = 12. Deel ik het nog een keer door twee. Kom ik op zes. En dan nog een keer zit ik op drie.”
“Precies. Je hebt vier factoren gebruikt, 2 x 2 x 2 x 3 = 24. Vier factoren. Dan verdien je dus 10 euro!”
“Ik krijg het geld terug van het lootje dat ik kocht, bedoel je?”
“Ja precies. Eigenlijk moet je meer dan vier factoren hebben om echt wat te winnen. Bij loterij 1 dan.”
“En hoe weet je wat een priemgetal is?”
“Een priemgetal kun je delen door zichzelf en 1, verder niet.”
“Ja, maar hoe weet ik dat van bijvoorbeeld ehm, 91? Is dat deelbaar door 11? Nee wacht 11 x 9 = 99. Ehm, is 91 deelbaar door zeven misschien?”
“Nou 10 x 7 = 70. 91 – 70 is 21. En eh… 3 x 7 = 21. 70 plus 21 is 91. Geen priemgetal Pap, 91 is deelbaar door 7, helaas, geen goed lot.”
“Ja maar hoe weet ik of 97 een priemgetal is? Als ik ga proberen te delen. Ik kan de even getallen overslaan, dus 3, nee, 5, nee, 91 is deelbaar door 7, dus lukt inderdaad niet voor 97, 9? Nee 11 x 9 = 99. 11 hadden we daarnet. Maar 13 misschien?”
“10 x 13 = 130, de helft is eh 50 plus 15 is 65. Hm, 2 x 13 erbij is 65 plus 26 is 91.. hee grappig, nee weer geen 97 maar wel weer die 91.”
“Dan weet ik nog niks. 17 proberen? Kom ik op 5 x 17 is 85, plus 17 is eh, 92. Nee ook niet. Kom we kunnen dat proberen met al die getallen ook even schrijven in code.”
“Je moet gewoon vanaf 2 alle getallen proberen en dan delen, en kijken of er een geheel getal uit komt.”
“Ah, dat kan in code met MOD, modulo.”
“Wat?”
“Modulo geeft aan dat als je deelt, of er een restgetal is. 7 / 5 is 1 rest 2. Met 7 modulo 5 krijg je dan de 2. Als er nul uit de modulo komt, is het deelbaar, anders dus niet. Dus 10 mod 5 is nul want 10 gedeeld door 5 is 2 rest nul. Je krijgt dus ‘de rest’ uit de modulo. Is wel handig.”
“Ok.. schrijf dan? Je kan trouwens tot de helft van het getal lopen, want je hoeft na de helft natuurlijk niet verder te proberen. Als je 10 deelt door 5 ben je wel klaar, je hoeft dan niet 6 of 7 en hoger nog te proberen.”
“Is goed.”
En ik schrijf de functie IsPriem:
public static bool IsPriem(int getal)
{
if (getal == 1) return false;
for(int i =2; i<(getal/2)+1; i++) {
if (getal % i == 0) {
return false;
}
}
return true;
}
“Wat doe je nou? Wat is een static? Waarom true en false?”
“public static.. dat is hoe je een functie schrijft in deze taal. We kunnen een getal in deze functie stoppen om te vragen of het een priemgetal is.”
“Dan heb je het maar voor 1 getal? Ik wil het weten voor alle getallen van 1 tot 100!”
“Ja, zo snel gaat programmeren niet. Eerst deze even testen met een getal. Stel 24, dan verwacht ik dat die dus false terug geeft.”
“False. En 17? True! Zo te zien werkt het. Goed zeg. Nu moeten we alleen nog een loopje hebben en alle priemgetallen bij elkaar optellen.”
“Ja, laten we meteen alle priemgetallen in een lijstje bewaren. Dat is handig voor de andere loterij.”
int waarde = 0;
List<int> PriemGetallen = new List<int>();
for (int getal = 1;getal <= 100; getal++) {
bool isPriem = IsPriem(getal);
if (isPriem)
{
waarde += getal;
Console.WriteLine("{0} {1} ", getal, waarde);
PriemGetallen.Add(getal);
}
}
Console.WriteLine("totaal is:{0}", waarde);
OUTPUT:
2 2
3 5
5 10
7 17
11 28
13 41
17 58
19 77
23 100
29 129
31 160
37 197
41 238
43 281
47 328
53 381
59 440
61 501
67 568
71 639
73 712
79 791
83 874
89 963
97 1060
totaal is:1060
“Whow. Je moet 1060 euro uitkeren voor al die priemlootjes zoon!”
“Oh, dat is niet zo mooi. Dan kan er niks naar het goede doel.”
“Nee, inderdaad. De andere manier eens proberen? Hoe bepalen we factoren van een getal?”
“Gewoon zoals ik zei. Je deelt een getal door een priemgetal en als het lukt ga je verder.”
“En we beginnen bij 2? En als het lukt weer door twee, en als het niet lukt, proberen we 3? 24 / 2 = 12. Dan weer 12 / 2 = 6”
“Ja, dat hadden we al. Maak weer zo’n functie die dan de factoren van een getal terug geeft. Je geeft het getal in en de priemgetallen, dan moet het lukken toch?”
“Eh, dus voor elk priemgetal dat we hebben proberen we te delen. Door twee, dan drie en zo verder. En zolang het lukt om te delen, delen we opnieuw door hetzelfde priemgetal. Tot het niet lukt, dan proberen we het volgende priemgetal. Even denken, foreach priemgetal, en dan een zolang… dus while delen lukt.. De functie geeft alle gevonden factoren terug. Kunnen dus dubbele in zitten.”
public static List<int> Factoren(int getal, List<int> priemgetallen)
{
List<int> deFactoren = new List<int>();
foreach(int priemgetal in priemgetallen) {
while(getal % priemgetal == 0) {
getal = getal / priemgetal;
deFactoren.Add(priemgetal);
}
}
return deFactoren;
}
“Eerst weer even proberen, we gooien er 24 in, kijken wat er uit komt.”
List<int> f24 = Factoren(24, PriemGetallen);
// Factoren uitprinten
foreach(int item in f24) {
Console.WriteLine(item);
}
OUTPUT:
2
2
2
3
“Ziet er goed uit. Nu voor de hele lijst van 100. Weer alle uitgedeelde prijzen optellen!”
int waarde2 = 0;
for (int getal = 1;getal <= 100; getal++) {
List<int> factoren = Factoren(getal, PriemGetallen);
if (factoren.Count == 4) {
waarde2 += 10;
}
if (factoren.Count == 5) {
waarde2 += 25;
}
if (factoren.Count >= 6) {
waarde2 += 100;
}
Console.WriteLine("{0} {1}", getal, factoren.Count);
}
Console.WriteLine("Totaal prijzengeld:{0}", waarde2);
OUTPUT:
1 0
2 1
3 1
4 2
5 1
6 2
7 1
8 3
9 2
10 2
11 1
12 3
13 1
14 2
15 2
16 4
17 1
18 3
19 1
20 3
21 2
22 2
23 1
24 4
25 2
26 2
27 3
28 3
29 1
30 3
31 1
32 5
33 2
34 2
35 2
36 4
37 1
38 2
39 2
40 4
41 1
42 3
43 1
44 3
45 3
46 2
47 1
48 5
49 2
50 3
51 2
52 3
53 1
54 4
55 2
56 4
57 2
58 2
59 1
60 4
61 1
62 2
63 3
64 6
65 2
66 3
67 1
68 3
69 2
70 3
71 1
72 5
73 1
74 2
75 3
76 3
77 2
78 3
79 1
80 5
81 4
82 2
83 1
84 4
85 2
86 2
87 2
88 4
89 1
90 4
91 2
92 3
93 2
94 2
95 2
96 6
97 1
98 3
99 3
100 4
Totaal prijzengeld: 420
“Hee!” zegt zoon. “49 is geen priemgetal?”
“Nee, 7 x 7 = 49.”
“Oh ja, natuurlijk. 420 euro! Dan houden we toch nog geld over voor het goede doel!”
“Je hebt behalve 64 trouwens nog een hoofdprijs, zie ik. 96 heeft er ook zes!”
“Hee ja, inderdaad. Zitten er nog meer in?”
“Zo te zien niet. Maar die tweede loterij met factoren is inderdaad beter voor het goede doel. Nou. Leuk he, programmeren?”
“Ja, handig! Bedankt pap! Enne, 97 is een priemgetal. Goed gekozen!”
Code te vinden op:
https://dotnetfiddle.net/qQmtkY