Primtal – Eratosthenes si

Eratosthenes var en græsk astronum og matematiker, som bl.a. fandt en måde/metode til at finde primtal på. Metoden kaldes ‘Eratosthenes si’.

Kort fortalt, så kan metoden forklares ved, at man

1. startede fra tallet 2 og fandt alle de tal, som 2 gik op i (2 tabellen).
2. Derefter fjernede man alle de tal, hvor 2 gik op, da de jo måtte være sammensatte tal.
3. Så gik man til næste naturlige tal, som ikke var blevet fjernet. Det var tallet 3.
4. Så skulle man finde alle de tal, som 3 gik op i (3 tabellen).
5. Derefter fjernede man alle de tal, hvor 3 gik op, da de jo måtte være sammensatte tal.
6. Så gik man til næste naturlige tal, som nu var tallet 5, fordi tallet 4 jo blev fjernet (under pkt. 2), da 2 gik op i 4.
7. Sådan fortsatte man.

Det er en meget langsommelig metode, men den virker.

Nedenstående kode bruger lidt det samme princip. Dog stopper koden, når den finder det første tal, som går op i tallet (tal). Kan du gennemskue koden?

# får brugeren til at indtaste tallet
tal = int(input("Find primtal op til og med tallet: "))

# hvis tallet (tal) er større end 1
if tal > 1:
    for i in range(2,tal+1):
        # sætter variabel prim til 1
        prim = 1
        for j in range(2,i):
            # Kontrol for, om i har divisorer
            if (i%j) == 0:
                # sætter variabel prim til 0, hvis i har divisor (j går op i i).
                prim = 0
                if prim == 0:
                    break
        # hvis tallet ikke har divisorer, så er prim stadig = 1. Derfor er tallet et primtal. 
        if prim == 1:
            print(i)

else:
  # hvis tallet (tal) er mindre end 1 eller
# lig med 1, så er det ikke et primtal
    print("Tallet er ikke stort nok.")

Opgave

• Forklar koden linje for linje for en anden eller lav en beskrivelse af koden på skrift.
• Afprøv koden i en compiler og indtast.
• Behøver man indtaste linje 14? Hvorfor/hvorfor ikke?
• Prøv at bytte print(i) ud med print(i, ", ", end = ''). Hvad sker der ved det?