Onsdag i neste uke får jeg utdelt hjemmeeksamen i faget Numerisk fysikk. Derfor prøver jeg å holde meg litt i Python-modus, i tillegg til at jeg naturligvis er i master-panikk-modus, så jeg tenkte jeg skulle gjøre et forsøk på å skrive en introduksjon til Python jeg også, med innretning mot fysikere. Eller matematikere.

Det første man må gjøre, er naturligvis å skaffe python. Det kan man for exempel laste ned fra www.python.org. Jeg må bare innrømme at jeg ikke har peiling på hvordan man installerer eller tar i bruk Python på en Windows-maskin, men jeg går ut fra det er overkommelig. På Mac, Unix og Linux er det bare å skrive

sudo apt-get install python

i terminalen, så er man i gang. På nokså kort sikt vil du antagelig også installere NumPy, som er en tilleggspakke for Python som lar deg gjøre matriseregning og slike ting. Igjen aner jeg ikke hvordan man gjør dette på Windows, men jeg mistenker at det er trivielt. Dedikerte lesere vil sikkert huske at jeg kastet bort en del tid på NumPy og SciPy tidligere i vår. SciPy fikk jeg aldri til å funke, men NumPy gikk bra, og jeg har aldri følt at jeg mangler noe.

Uansett, for å følge med på denne artikkelen trenger man bare Python, og en editor. En editor er et hvilket som helst program som kan redigere rene tekst-filer. Notepad, for eksempel, eller Vi, emacs, TextEdit, TextMate, TexShop eller hvasomhelst.

Det første vi vil gjøre, er å åpne en ny tekstfil, som vi vil skrive programmet vårt i. Tradisjonelt sett pleier man å begynne med et program som skriver «Hello, World» på skjermen, men jeg tror vi skal sette oss litt høyere mål. Ikke bare fordi vi er tøffe i trynet, men som jeg sa, jeg retter meg mot fysikere (egentlig retter jeg meg mot Matteus), og dermed kan vi umiddelbart gå løs på et litt mer solid eksempel, da litt matte ikke er noen hindring.

Målet vårt er å skrive et program som regner ut alle primtallene opp til N. For å gjøre det benytter vi teknikken som kalles Eratostenes sil. Det går helt enkelt ut på at vi begynner med 2, som vi vet er et primtall. Deretter fjerner vi alle tall mellom 2 og N som er delelige på 2. Så går vi videre til neste tall, 3, som også er et primtall, siden det ikke er delelig på 2. Vi fjerner alle tall som er delelige på 3, og går videre til 5, som er neste gjenværende tall. Vi vet at det ikke er delelig på 2 og 3, og det er dermed et primtall. Og slik holder vi på. Dette er ikke den mest effektive måten å finne primtall på, tror jeg, men det er den jeg husker, og den er ganske enkel å programmere.

Vi begynner med å definere N, som vi gjør ved å skrive

N = 100

Hvis man har bakgrunn fra andre språk vil man kanskje lure på om vi ikke skal definere hva slags størrelse dette er snakk om, om det er int eller float eller et komplekst tall, eller kanskje noe helt annet. Det trenger vi ikke. Akkurat som du og jeg, synes Python det er helt åpenbart at her har vi å gjøre med et heltall. Ferdig arbeid.

Det neste vi må gjøre er å lage oss en liste over alle tallene opp til N. Det gjør vi ved hjelp av den innebygde range-funksjonen. Hvis N = 100, og vi skriver

M = range(N)

vil variabelen M inneholde en liste over alle tallene fra og med 0, til og med 99. Vi vil imidlertid helst ha en liste over alle tallene fra og med 2, til og med 100. Derfor skriver vi

M = range(2,N+1)

Grunnen til at vi hele veien ønsker å bruke N i stedet for å skrive 100, er naturligvis at da blir det mye enklere å tilpasse programmet senere, men det er slikt en fysiker allerede vet. Det neste vi må gjøre, er å lage to tomme lister, som vi skal putte tall i senere.

P = []
Q = []

En liste kan vi manipulere på mange måter. Vi kan for eksempel hente ut element nummer x ved å skrive M[x], eller vi kan legge til et element, n, bakerst i listen, ved å skrive M.append(n). Begge disse metodene skal vi benytte nå, i det som kalles en løkke, eller en loop. Men først et bittelite eksempel:

A = [1,2,3,4]
for a in A:
  print a

Det denne løkken gjør, er at den tar for seg listen A, og går gjennom løkken en gang for hvert enkelt element. Hver gang den går gjennom, vil a representere det aktuelle elementet i listen. Det er verdt å merke seg at hva man kaller variablene spiller ingen rolle. Jeg kunne like godt ha skrevet

brunost = [1,2,3,4]
for hvitost in brunost:
  print hvitost

og utputten, eller hva det nå heter på norsk, ville blitt den samme. Det denne løken gjør, er simpelthen at det skriver hvert enkelt element til kommandolinjen. Den skriver altså ut alle tallene i listen. Men det er ikke så interessant, så vi går videre til en litt barskere løkke. La meg bare først nevne at store og små bokstaver ikke er det samme. Variabelen N er ikke den samme som variabelen n.

Vi skriver

for m in M:
  if m not in Q:
    P.append(m)
    for x in xrange(N/m+2):
      Q.append(X*m)

Det vi gjør her, et først at vi sjekker om tallet m finnes i Q. Hvis ikke, legger vi det til i P, som til slutt vil utgjøre listen over primtallene våre. Deretter lager vi en ny løkke inni den gamle, som går igjennom alle tallene fra 0 og opp til N/m+2, og legger til alle heltallige multipler av m i Q. Q vil dermed utgjøre listen over tall vi vet ikke er primtall.

Fire kommentarer:

Igjen, hvis man har bakgrunn fra andre språk vil man kanskje tenke at innrykkene kun er der for å øke lesbarheten. Det er ikke tilfelle. I Python bruker man ikke paranteser eller end-kommandoer for å avslutte løkker, og derfor må man ha innrykk. Alt som er på samme nivå i løkken må ha samme mengde innrykk. Det er anbefalt å bruke fire mellomrom pr. nivå, og derfor er det enklest å skaffe seg en editor som skjønner Python. emacs for eksempel.

xrange er på en måte det samme som range, men ikke helt. range lager en faktisk liste over tall, som man kan lagre i en variabel. xrange, derimot, lager en abstrakt liste som man kan gå gjennom i en løkke, men som ikke bli lagret noe sted. Fordelen med xrange er at den bruker mindre minne, hvis det er snakk om voldsomt store tall.

Jeg sa innledningsvis at vi skulle fjerne alle tallene som er heltallige multipler av primtall. Det viser seg imidlertid at det kan bli litt fuckup hvis man begynner å fjerne tall fra en liste samtidig som man looper over den samme listen. Derfor legger vi til de tallene som ikke er primtall i Q, og så sjekker vi mot den listen for hver runde.

Og til slutt, grunnen til at jeg går opp til N/m+2 er at N og m er heltall. Python er ganske smart, men ikke så smart som oss. Derfor tror Python at N/m også skal være et heltall, og runder ned. I tillegg har vi det at både range(n) og xrange(n) går opp til n-1, med mindre vi sier noe annet. Disse to tingene kan føre til at vi ikke sjekker alle tallene helt til topps, og derfor vil 999 og 1000 komme ut som primtall, noe de ikke er.

Men nå har vi i alle fall endt opp med et kjørbart program. Hvis vi bare hiver på en kommando som gir oss listen over tallene, er vi egentlig ferdige, og resultatet ser slik ut:

#!/usr/bin/env python

N = 100

M = range(2,N+1)
P = []
Q = []

for m in M:
  if m not in Q:
    P.append(m)
    for x in xrange(N/m):
      Q.append(X*m)

print P

Den første linjen har vi lagt til for at Unix-systemer skal skjønne at det er Python vi har med å gjøre. Jeg vet ikke om den har noen funksjon på Windows. Så må vi lagre dette. Det gjør vi på vanlig måte for tekstfiler, bare at vi passer på å få med endelsen .py. Primtall.py er et bra navn.

Utfordringen nå er å kjøre programmet, og igjen aner jeg ikke hvordan det foregår på Windows, men jeg ser for meg at det ikke er spesielt vanskelig, og jeg regner med noen her vet det, og kan forklare. På alt annet åpner man terminalen, manøvrerer seg frem til det aktuelle mappen, og skriver

python primtall.py

Seså, var ikke det enkelt? Jeg håper i alle fall det. All tilbakemelding mottas med takk.

-Tor Nordam