Level 3Primtall og effektivitet

Skrevet av: Martin Strand

Kurs: Python
Tema: Tekstbasert, Kryptografi
Fag: Matematikk, Programmering
Klassetrinn: 8.-10. klasse, Videregående skole

Introduksjon

I matematikktimene har du lært om primtall, altså tall som er slik at de bare kan deles av seg selv og 1. Nå skal vi se hvordan vi kan undersøke om et vilkårlig heltall er et primtall eller ikke.

Når vi skal kryptere data er vi ofte avhengige av å jobbe med store primtall, og vi vil få bruk for det i senere oppgaver. For å jobbe med primtall, må vi først ha en måte å finne dem på.

Steg 1: Rest etter divisjon

Den grunnleggende måten vi gjør dette på er å dele på andre tall. La oss si at vi vil sjekke tallet 15. Tallet 2 går ikke opp i 15, så da sier vi at vi får en rest. Åpne IDLE, men uten å lage en ny fil. Der det står >>> kan vi skrive inn kode for å se hva den gjør.

checkSjekkliste

Steg 2: Enkel prøvedivisjon

Over fikk vi 0 når vi regnet ut 15 % 3. Det betyr at 3 går opp i 15, og altså er ikke 15 et primtall. Det kan vi utnytte for å sjekke om noe er et primtall. Vi kan dermed lage en funksjon som tar inn et tall n og sjekker om alle tall som er mindre enn n går opp i n.

checkSjekkliste

  • def is_prime(n):
        for i in range(2, n):
            if n % i == 0:
                return False
        return True
      
    print(is_prime(15))
    print(is_prime(29))
    

Steg 3: Forbedret prøvedivisjon

Vi har laget et program som gir riktig svar, men som bruker veldig lang tid på å gjøre det. Da må vi se om vi kan øke hastigheten på koden vår, og her kan vi få hjelp av et enkelt matematisk argument. Si at et tall nn er et produkt av to andre, slik at n=pqn = pq. Da må enten pp eller qq være mindre enn (eller lik) kvadratroten av nn.

(Hvis du er interessert, her er en forklaring på hvorfor: Hvis begge er større, så får vi følgende utregning: n=pq>nn=nn = pq > \sqrt{n} \sqrt{n} = n. Da har vi n>nn > n, og det er umulig. Derfor må minst en av p og q være mindre eller lik.)

I Python kan vi regne ut kvadratrøtter ved å bruke funksjonen sqrt som finnes i math-biblioteket. Siden sqrt kan returnere et flyttall, bruker vi også funksjonen ceil fra samme bibliotek for å runde opp til nærmeste heltall.

checkSjekkliste

from math import sqrt, ceil

def is_prime(n):
    for i in range(2, ceil(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
  
print(is_prime(15))
print(is_prime(29))

Steg 4: Flere forbedringer?

Vi kan ennå gjøre koden vår raskere ved å sjekke for 2, og deretter hoppe over alle partallene. For å gjøre det enkelt, kan vi legge til en tredje parameter til for-løkka vår, og som sier hvor mye den skal øke hver gang. Standardverdien er 1, men vi endrer den til 2.

checkSjekkliste

from math import sqrt, ceil

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, ceil(sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
  
print(is_prime(15))
print(is_prime(29))

Men, hvorfor skal vi stanse her? Vi kan jo også dele på 3 og 5 til å begynne med, og da trenger vi ikke sjekke noen av tallene over som selv er delelige på 3 eller 5. Og slik kan vi fortsette, helt til vi kun tester med tallene som selv er primtall. Og, vi vet jo allerede hvordan vi finner små primtall. Vi kan altså prøve oss fram med den følgende koden.

  • from math import sqrt, ceil
    
    def is_prime(n):
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for i in range(3, ceil(sqrt(n)) + 1, 2):
            if is_prime(i):
                if n % i == 0:
                    return False
        return True
      
    print(is_prime(15))
    print(is_prime(29))
    
  • from math import sqrt, ceil
    
    def is_prime(n):
        small_primes = [2, 3, 5, 7, 11, 13, 17, 19]
        if n in small_primes:
            return True
        for prime in small_primes:
            if n % prime == 0:
                return False
        for i in range(21, ceil(sqrt(n)) + 1, 2):
            if is_prime(i):
                if n % i == 0:
                    return False
        return True
      
    print(is_prime(15))
    print(is_prime(29))
    

    Denne siste koden er den raskeste vi har hatt hittil, og hvis man skal sjekke veldig mange tall på kort tid, gjør den siste forbedringen vår at det vil gå ganske raskt.

  • (...)
    def is_prime(n):
        if not (isinstance(n, (int, long)) and n > 1): 
            return False
        small_primes = [2, 3, 5, 7, 11, 13, 17, 19]
    (...)
    

Bonus

Ikke overraskende kan vi fortsatt gjøre noen forbedringer, men her må du gjøre mye av tenkingen og programmeringen selv. Her skal vi erstatte listen av små primtall med en liste datamaskinen lager selv. Det gjør vi ved hjelp av en algoritme som kalles Eratosthenes sil. Begynn med å lage en lang liste av boolske verdier (True/False) opp til den verdien vi skal sjekke.

def eratosthenes(max):
    candidates = [True] * max

Vi bruker indekseringen av listen som tolkning av hvilket tall vi ser på. Start derfor med å sette candidates[0] = False og candidates[1] = False, siden 0 og 1 ikke regnes som primtall. Deretter er logikken som følger, og det er du selv som må oversette dette til Python-kode:

for hvert element i candidates, opp til kvadratroten av max:
    hvis elementet er True: (f.eks. 7)
        sett alle multipler av elementet til False (14, 21, 28, ...)
 gjennom listen og lag en ny som består av tallene som fortsatt er True
returner den nye listen

Når du er ferdig med å implementere rutinen din, kan du sette den inn i kodefilen vi laget over, og endre koden slik at den ser slik ut:

from math import sqrt, ceil

def eratosthenes(upper_limit):
    // din kode her

def is_prime(n, small_primes=[2, 3, 5]):
    if not (isinstance(n, (int, long)) and n > 1): 
        return False
    if n in small_primes:
        return True
    for prime in small_primes:
        if n % prime == 0:
            return False
    start = small_primes[-1] + 2
    for i in range(start, ceil(sqrt(n)), 2):
        if is_prime(i):
            if n % i == 0:
                return False
    return True

upper_bound = 1000000
small_primes = eratosthenes(upper_bound)

print(is_prime(15, small_primes))
print(is_prime(29, small_primes))

Effekten av det vi har gjort nå er at vi har en liste med små primtall, og den kan vi gjenbruke så mange ganger vi vil. Dersom vi skal teste veldig mange tall, har vi derfor gjort en stor del av det arbeidet én gang for alle.

Lisens: CC BY-SA 4.0

Forbedre denne siden

Funnet en feil? Kunne noe vært bedre?
Hvis ja, vennligst gi oss tilbakemelding ved å lage en sak på Github eller fiks feilen selv om du kan. Vi er takknemlige for enhver tilbakemelding!