Räkna ut primtal i Python & Scratch
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.
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.
Relaterat
Senaste nyheterna och inläggen
CyberInfo Sverige är ett IT- och medieföretag i nordvästra Skåne som tillhandahåller böcker, utbildningar, nyheter och konsulttjänster inom Linux, BSD och programmering.
CyberInfo Sverige är godkänd för F-skatt, är momsregistrerat och innehar
utgivningsbevis för webbplatsen www.cyberinfo.se.