Övningar med listor

Alla positiva heltal som inte själva är primtal går att dela upp i produkter av primtal. Detta kallas primtalsuppdelning. Ex: 28 = 2*2*7, 72 = 2*2*2*3*3, 39 = 3*13

Detta kan bland annat användas för att göra listor på primtal och för att göra snabbare funktion för att finna största gemensamma delare.

Övning 2.13
Lägg till en funktion till modulen diskret_matematik för  att skapa en funktion som utför primtalsuppdelning enligt nedanstående pseudokod:

def primtalsuppdelning(n):
    Skapa en tom lista kallad primtal
    sätt variabeln p till 2
    så länge som p är mindre eller lika med n:
        om n är jämnt delbart med p:
            lägg till p i listan primtal
            dividera n med p
        annars :
            öka p med ett
            
    returnera primtal

Övning 2.14
Använd primtalsuppdelningen ovan till att göra en betydligt effektivare version av funktionen sgd(a, b). Byt ut den befintliga mot denna version. Pseudokod:

def sgd(a, b):
    sätt storst till det största talet av a och b samt
    minst till det minsta
        
    om storst jämnt delbart med minst returnera minst
    primtalsuppdela minst och spara resultatet i listan prim
    antag att största gemensamma delare, sgd är 1
    för alla tal p i prim :
        om storst jämnt delbart med p :
            dela storst med p
            multiplicera sgd med p
            
    returnera sgd

Övning 2.15
Uppdatera main() i diskret_matematik med tester av primtalsuppdelningen och testkör.

Uppgift 2.5
Skriv ett program som hittar primtal genom att använda Eratosthenes såll.

Bild: Wikipedia