Att koda program som visar eller räknar ut primtal är ett bra sätt att lära sig om loopar på. Dessutom är det ju både praktiskt och roligt att göra. För visst är det väl bra att ha ett program nära till hands som visar om ett visst tal är ett primtal eller inte? Dessutom tränar det hjärnan att tänka logiskt.

Först lite matte

Ett primtal är ett heltal som inte går att dela med något annat heltal än sig självt och 1 utan att få någon rest. Exempelvis är 5 ett primtal, eftersom vi kan bara dela 5 med sig själv, $\frac{5}{5 } = 1$, och ett, $\frac{5}{1} = 5$. Alla andra tal vi testar att dela med kommer att ge en rest.

Det enklaste sättet för att se om ett givet tal, $n$, är ett primtal eller inte, är således att testa att dela talet $n$ med alla tal mellan $2$ och $n-1$.

Låt oss först börja med ett tal som inte är ett primtal, talet 9, och demonstrera detta.

Talet 9 är alltså inte ett ett primtal eftersom $9/3=3$ och gav således ingen rest. Om vi istället tar ett primtal, till exempel talet 5 och gör samma procedur så kommer vi inte hitta något tal mellan 2 och $5-1$ som inte får en rest.

Således har vi att talet 5 är ett primtal. Nu är det dags att göra om denna kunskapen om primtal till kod.

Scratch

Vi börjar med ett litet program i Scratch som svarar på om det tal man matar in är ett primtal eller inte. Programmet börjar med att sätta en variabel c till 2, det första talet vi ska testa att dividera med. Därefter ber vi programmet fråga användaren efter ett tal, det tal som vi vill veta är ett primtal eller inte. Därefter kommer programmets loop. Denna loopen körs tills dess att c = answer, alltså tills dess att c är lika med talet som vi vill veta om det är ett primtal eller inte. Kontrollen ifall det är ett primtal eller inte har ju inte skett ännu, den sker inuti loopen, därför blir det samma sak som $n-1$. Nu när vi är inuti loopen gör vi kontrollen och uträkningen. För att kontrollera om vi får någon rest använder vi modulo-operatorn i Scratch. Uträkningen säger alltså answer modulo c, vilket betyder i princip answer delat med c, fast istället för svaret vill vi bara veta hur mycket vi får i rest. Får vi noll i rest här så är det inget primtal, då går vi vidare med att skriva ut texten “Not a prime number” samt stoppar resten av programmet. Skulle vi istället få en rest så går vi vidare till change c by 1, alltså öka på c med 1. I detta första varvet blir det alltså $2+1=3$. Så c innehåller nu istället värdet 3. Nu börjar loopen om och fortsätter så här tills dess att c = answer. Får vi inte noll i resten på något utav varven i slingan så är faktiskt talet ett primtal och texten “Woho, that is a prime number” skrivs ut på skärmen.

Programmet ser ut som nedan och kan nås på länken primefinder on Scratch.

primefinder on Scratch

Python

Som med allting annat när vi programmerar så finns det oändligt många olika lösningar på samma problem. Här kommer jag visa två lösningar. Den sista av dessa lösningar, med else-satsen som hör till for-loopen får jag tacka en av mina läsare av boken Grunderna i programmering för. Hon skrev till mig och hade lite problem med en programmeringsuppgift, just en sådan här om primtal. Under tiden jag klurade på ett bra svar så hittade jag att man faktiskt kan använda else som en del utav en for-loop i Python. Detta gör att man kan skriva mycket kortare lösningar. Här nedan visas först ett program som liknar Scratch-programmet ovan, det vill säga att programmet frågar efter ett givet tal. Därefter kontrollerar programmet om talet är ett primtal eller inte och skriver ut svaret på skärmen. Programmet börjar med att fråga efter ett heltal. Därefter startar en for-loop med en range från talet 2, upp till, men inte inkluderat det tal vi angett. Väl inne i loopen görs samma kontroll som vi gjorde i Scratch-programmet, det vill säga kontrollerar ifall talet n modulo i = 0 där i startar på två och räknar upp till talet vi angav (men inte inkluderat talet vi angav). Om vi får ett svar här som ger 0 i rest, så är det inte ett primtal och detta skrivs ut skärmen med texten “is not a prime number” och avslutar samtidigt programmet. Om inget svar fås där vi får 0 i rest så är det ett primtal och talet tillsammans med texten “is a prime number” skrivs istället ut på skärmen. Programmet visas här nedanför.

#!/usr/bin/env python3

n = int(input("Enter a number: "))
    
for i in range(2, n):
    if (n%i == 0):
        quit (str(n) + " is not a prime number")
print (n, "is a prime number")

Python, alla primtal upp till 100

Som jag skrev tidigare i detta inlägg så måste jag tacka en av mina läsare för idén att korta av ett program som skriver ut alla primtal upp till 100 till endast några få rader. Att kunna använda else direkt på en for-loop har visat sig vara riktigt praktiskt. Det är få andra språk man kan göra så här i. Notera att else-satsen hör till for-loopen.

#!/usr/bin/env python3
for n in range(2,101):

    for a in range(2,n):
        if (n%a == 0):
            break
    else:
        print(n, "is a prime number")

När detta programmet körs så få vi en lista med alla primtal upp till 100.