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.
\[\frac{9}{2} = 4.5 \qquad \frac{9}{3} = 3\]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.
\[\frac{5}{2} = 2.5 \qquad \frac{5}{3} = 1.666... \qquad \frac{5}{4} = 1.25\]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.
Tyckte du om den här artikeln? Då kanske du även tycker om någon av våra böcker.
Relaterat
-
Python och trigonometri
Lite uppfräschning av trigonometri och Python är aldrig fel. Här får vi lära oss hur man kan rita upp rätvinkliga trianglar – direkt i Python – om vi känner till två av sidorna. För detta kommer vi att använda modulerna turtle och math.
-
Python i Windows utan installation
Det går att använda Python i Windows, även utan att installera det. Detta är användbart om du har en dator där du inte har rättigheter att installera program. Det kan till exempel vara en skoldator eller arbetsdator.
-
Ett primtalsprogram i C
Här ska vi få en kort introduktion till programspråket C genom att göra ett litet enkelt primtalsprogram. Program består utav tre filer. Två styck källkodsfiler och en styck header-fil. I header-filen lägger vi något som kallas för funktionsprototyper. En funktionsprototyp använder man för att tala om för programmet hur en funktion ser ut, det vill säga vilka argument funktionen tar samt vilken datatyp den returernar. Detta gör gör man för att slippa lägga funktionen överst i samma fil som
main()
. Header-filen döper vi till skrivprm.h. -
En introduktion till FIFO
FIFO står för First In, First Out, och är en typ av rörledning som vi kan skapa på systemet som går att använda mellan helt orelaterade processer. FIFOs fungerar som så att en fil skapas på hårddisken i systemet. Processerna som ska kommunicera med varandra använder sedan den filen. En annan fördel med FIFOs är att vi kan använda dem tillsammas med redan befintliga program. Där vanliga rörledningar inte räcker till kan man ofta använda just FIFO.
-
Ny bok om C-programmering
Efter 18 månader är äntligen boken C-programmering i Linux, macOS, BSD och Solaris klar! Detta har både varit mitt största, mest avancerade och roligaste bokprojekt någonsin. Inte nog med att boken har tagit 18 månader att slutföra, den har även tagit halva min lägenhet i besittning, i form av både nya och äldre datorer. All kod i boken har testkörts på åtta olika datorer av olika arkitekturer. Detta för att säkerställa att koden är så portabel och standardiserad som möjligt. Men det har utan tvekan varit värt alla laborationer. Jag har lärt mig så mycket under resans gång, så bara kunskapen i sig är värt allt arbetet.
Senaste nyheterna och inläggen
-
Stort deltagande på årets Gubbdata
I helgen var det Gubbdata i Lund – ett av Sveriges största demoparty. På plats fanns cirka ett hundra deltagare, alla med en passion för retrodatorer.
-
Tvåfaktorsautentisering vid SSH-inloggning
Med hjälp av en PAM-modul går det att aktivera tvåfaktorsautentisering i Linux med exempelvis Google Authenticator-appen. Linuxsystemet kräver då både användarens lösenord samt ett engångslösenord. Det går även att kombinera en SSH-nyckel med ett engångslösenord.
-
Affinitys prisvärda program
Det finns alternativ till Adobes dyra programsviter för kreativt skapande. Affinity har tre program som alla kan mäta sig med Adobes motsvarigheter. Dessa är Affinity Photo, Affinity Designer och Affinity Publisher.
-
Tjänster på användarnivå i Linux
I Linuxdistributioner med systemd går det att köra tjänster som vanliga användare. Med något som heter lingering går det dessutom att köra tjänster även om den aktuella användaren inte är inloggad.
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, säkerhet och programmering.
CyberInfo Sverige är godkänd för F-skatt, är momsregistrerat och innehar
utgivningsbevis för webbplatsen www.cyberinfo.se.