naar een programma van Henk Pfaltzgraff
(e-mail: henk@henkshoekje.com / url: http://www.henkshoekje.com)
- Wat is een priemgetal
Opdracht 1 - De functie fPart
Opdracht 2
Opdracht 3
Opdracht 4 - Priem of niet-priem
Opdracht 5 - Het echte onderzoek naar primaliteit
Opdracht 6
Opdracht 7
Opdracht 8 - Andere TI83-programma's
- Download
We geven direct maar een
| Definitie Een geheel getal n > 1 is een priemgetal (is priem) als het slechts deelbaar is door 1 en door zichzelf (de enige delers van n zijn dus 1 en n zelf). |
Gevolg
Een priemgetal heeft precies twee delers.
| Stelling 2 is het enige even priemgetal. |
Bewijs:
a. 2 heeft slechts delers 1 en 2. Dus 2 is een priemgetal.
b. Zij n een even getal groter dan 2. Dan is n te schrijven als n = 2·k (met k > 1).
Het getal n heeft dus zeker de delers 1, 2 en k.
n (een getal groter dan 2) is dus geen priemgetal. ¨
We hoeven dus niet naar de even getallen te kijken als we priemgetallen willen
zoeken.
Dus bekijken we 3, 5, 7, 9, 11, 13, …
Van elk van deze getallen kunnen we nu nagaan of ze een deler hebben die kleiner is dan
het getal zelf (maar groter dan 1).
Zo’n deler heet een echte deler.
We zullen hiervoor natuurlijk een TI83-programma gebruiken.
Als je bijvoorbeeld wilt onderzoeken of 1009 een priemgetal is, hoeveel (oneven) getallen moet je dan gebruiken als deler van 1009?
En als je 10009 neemt?
Zou het ook korter (met minder) kunnen?
Schrijf de echte delers van 945 op.
Ontbind 945 dan telkens met behulp van deze delers in een product van twee factoren (dus bijvoorbeeld: 945 = 3 * 315).
Heb je nu alle ontbindingen dubbel opgeschreven?
Zo ja, kijk dan eens of het met minder kan.
Verklaar waarom de grens van de in eerste instantie te gebruiken factoren ligt bij Ö945 (= 30,74).
We kunnen de TI83-functie fPart gebruiken om na te gaan of een getal a een deler is van een getal b.
Hoe gebruik je fPart daarvoor?
| Kijk om te beginnen eens naar de basis van een
TI83-programmaatje. (>>>) Op de lege regel tussen Else en End kunnen we dan onderzoeken of het ingevoerde getal n een priemgetal is. |
 |
Omdat het programma bij invoer van het getal 2 (of minder) stopt, is het mogelijk het programma ook zonder If..Then..Else..End op te zetten:
Prompt N
If N£ 2:Stop *
<.rest van het programma.>
Maak met dit laatste een begin van een TI83-programma.
Geef het programma bijvoorbeeld de naam PNP (PriemNietPriem).
Opmerking
Als er na een If-statement slechts één ander statement moet worden uitgevoerd, zoals in de regel met een * hierboven, dan worden beide statements vaak op dezelfde regel geplaatst, gescheiden door een ‘:’.
[einde Opmerking]
In de <.rest van het programma.>
onderzoeken we eerst of n een even getal is. We gebruiken dan 2 als deler d
van het getal n.
Maar als dat niet zo is (dus als n niet even is), kunnen we alle oneven getallen d
van 3 tot Ön gebruiken.
We krijgen dan iets als (in "pseudo taal"):
ALS fPart(n/2) = 0 DAN
<.n is geen priem getal.> … (1)
ANDERS
<.gebruik oneven getalllen tot Ö(n) voor het onderzoek.> … (2)
END
Het eerste stukje, tot en met (1), kan al worden opgenomen in het programma:
If fPart(N/2) = 0
Then
Disp "NIET-PRIEM (EVEN)"
Hierna kan het programma opnieuw worden doorlopen.
Daarom springen we naar het einde van het programma via
Goto P
End
Op het einde van het programma plaatsen we dan:
Lbl P
Pause "[Enter]"
Goto O … de ‘O’ van Opnieuw!
Aan het begin van het programma moet dus:
Lbl O
ClrHome
staan.
Kijk nu eens of het programma werkt als je voor n een even getal kiest.
Kijk ook eens wat er gebeurt als n oneven is (niets?).
Vergelijk zo nodig het programma dat je tot nu toe hebt ingevoerd, met:
Lbl O
ClrHome
Prompt N
If N£ 2:Stop
If fPart(N/2)=0
Then
Disp "NIET-PRIEM (EVEN)"
Goto P
End
<.de rest.> Hier staat dus een lege regel!
Lbl P
Pause "[ENTER]"
Goto O
4. Het echte onderzoek naar primaliteit
Het eigenlijke onderzoek naar het al of niet priem zijn van een oneven getal (de primaliteit van zo’n getal) vindt plaats in het programmadeel <.de rest.> (zie het einde van paragraaf 3).
Het is niet nodig de waarde van Ön te berekenen; kijk maar in de eerste regel hieronder:
For(D,3,Ö(N),2)
If fPart(N/D)=0
Disp "NIET-PRIEM"
End
| Opmerking In plaats van de bovengrens Ö(N) wordt vaak int(Ö(N))+1 gebruikt ( int is te vinden via [MATH]<NUM>) ). Wat is het effect hiervan? [einde Opmerking] |
 |
Als er geen enkele deler gevonden is, dan wordt bovenstaande For-lus geheel doorlopen.
Echter, de onderstaande invulling van <.de rest.> (zie het einde van paragraaf 3) voldoet niet.
For(D,3,Ö(N),2)
If fPart(N/D)=0
Disp "NIET-PRIEM"
End
Disp "...IS PRIEM"
Waarom voldoet dit programmadeel niet?
| Aanwijzing Hiernaast zie je de uitvoer als n = 99. (>>>) |
 |
Probeer een verklaring te vinden voor het feit dat er in dit geval twee keer "NIET-PRIEM" komt.
Lees daarna pas verder!
Het probleem dat gesignaleerd is in Opdracht 6, is (onder meer)
daarin gelegen, dat, wanneer de eerste echte deler van n gevonden is, toch de
volgende delers (zonder dat dat werkelijk nodig is!) in de test worden gebruikt. De FOR-lus wordt niet onderbroken!
Om dit te voorkomen kunnen we een (zogenoemde) vlag gebruiken die aangeeft dat de
eerste echte deler gevonden is.
Vlaggen nemen alleen de waarde 1 (vaak gebruikt in de betekenis "waar")
en 0 (vaak gebruikt in de betekenis "onwaar") aan.
Om het doorlopen van de lus te stoppen moeten we uit de lus springen met Goto, naar een label (Lbl) buiten die lus.
Overigens is het aan te raden, voor het ingaan van de lus, een waarde aan de
vlag toe te kennen.
We gebruiken hieronder de variabele V voor de vlag.
V bepaalt dus in dit geval of we een priemgetal hebben gevonden of niet!
Bekijk de volgende programmaregels voor <.de rest.>.
| 1->V For(D,3,Ö (N),2) If fPart(N/D)=0 Then Disp "NIET-PRIEM" 0->V Goto U End End Lbl U If V=1:Disp "...IS PRIEM" |
* * * * * * * |
De regels voorzien van *
zijn nieuw in vergelijking met het programmadeel in Opdracht 6.
Ga na, dat dit programmadeel inderdaad doet wat we willen.
Hieronder laten we het programma PNP (met de gebruikelijke ingesprongen regels) in z’n geheel volgen:
| Lbl O ClrHome Prompt N If N£ 2:Stop If fPart(N/2)=0 Then Disp "NIET-PRIEM (EVEN)" Goto P End 1® V |
For(D,3,Ö (N),2) If fPart(N/D)=0 Then Disp "NIET-PRIEM" 0® V Goto U End End Lbl U If V=1:Disp "...IS PRIEM" Lbl P Pause "[ENTER]" Goto O |
Wat is de "betekenis in woorden" als de vlag V de waarde 0 heeft?
En wat als de waarde van V gelijk is aan 1?
Controleer het programma door enkele oneven getallen in te voeren.
Op de Huispagina van Henk Pfalzgraff (http://www.henkshoekje.com) staan drie andere TI83-programma’s die te maken hebben met priemgetallen.
Op de pagina http://www.henkshoekje.com/G1_Delers.htm staat
(G1) DELERS: alle delers van een getal
en op http://www.henkshoekje.com/G2_Priemrij.htm
(G2) PRIEMRIJ: geeft alle (maar bedoeld is "een groot aantal") priemgetallen vanaf een gegeven getal
(G?) DMOPRIEM: een doorlopende priemgetallen generator.
Het programma PRIEMRIJ was uitgangspunt van het programma PNP op dit werkblad.
Opmerking
Om deze programma’s te kunnen gebruiken heb je het programma TI-Graph Link van Texas Instruments nodig. Met dit programma en een speciale kabel kan je TI-programma’s tussen een PC en de TI-83 uitwisselen.
Zie verder: http://www.ti.com/calc/docs/link83.htm (website van Texas Instruments).
[einde Opmerking]
6. Download
Het programma PNP kan via deze website (eventueel samen met andere TI-83 programma's) in
één bestand worden gedownload.
Zie ook de opmerking hierboven.
Klik hier
om het downloaden te starten [ZIP-bestand].
Dit werkblad is NIET MEER beschikbaar in PDF-formaat.
prgmpnp.pdf [ca.
28Kb]
[prgmpnp.htm] laatste wijziging op: 19-01-18