Programmeringens grunder

Kapitel 14: Eratosthenes såll

Ett primtal är ett heltal som är minst 2 och delbart endast med 1 och sig självt. Till exempel är talen 5, 11 och 29 primtal. Talet 12 är däremot inte ett primtal, eftersom 3*4 = 12.

Målet med detta kapitel är att skapa ett program som söker primtal. Till detta använder vi en algoritm som också går under namnet Eratosthenes såll. Den söker alla primtal mellan 2...n, där n står för den önskade övre gränsen.

Sållets funktion

Eratosthenes såll upprätthåller en bokföring över talen 2...n. Algoritmen går igenom talen från det minsta till det största. Vid varje tal i markerar algoritmen multiplerna av talet 2*i, 3*i, 4*i etc. med ett kryss. Krysset betyder att ifrågavarande tal inte är ett primtal, eftersom det är delbart med i. När algoritmen slutar känner man igen primtalen på att de inte har ett kryss.

Låt oss till exempel granska hur Eratosthenes såll fungerar när n är 100. Då söker algoritmen efter alla primtal mellan 2...100. Detta är algoritmens utgångsläge:

Algoritmen kryssar först för multiplerna för 2, dvs. 4, 6, 8, etc.

Sedan kryssar algoritmen för multiplerna för talet 3, dvs. 6,9,12, etc.

Algoritmen går vidare på motsvarande sätt tills den har gått igenom alla tal in intervallet 2...100. Då är bokföringens innehåll följande:

Detta innebär att primtalen i intervallet 2...100 är:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Genomförande av sållet

För att vi ska kunna programmera Eratosthenes såll behöver vi ett sätt att lagra bokföringen över talen i minnet. Ett bra sätt att göra detta är att skapa en lista som har en plats för varje tal i bokföringen. Vi kan skapa listan så här:

sall = [0]*(n+1)

Elementen i denna lista har numrerats 0, 1, 2, ..., n, och varje element börjar med talet 0. Meningen är att sall[x] innehåller information om talet x har kryssats för. Värdet 0 betyder att talet inte har kryssats för och värdet 1 betyder att talet har kryssats för. Märk väl att vi inte använder listans element 0 och 1 under algoritmen, eftersom vi behöver bokföringen först från och med element 2.

Följande kod genomför Eratosthenes såll:

n = 100
såll = [0]*(n+1)
for i in range(2,n+1):
    for j in range(2*i,n+1,i):
        sall[j] = 1

Kodens huvudslinga går igenom talen 2...n, och vid varje tal i markerar den kapslade slingan att multiplerna 2*i, 3*i, 4*i etc. av talet inte är primtal.

Efter detta kan vi skriva ut de identifierade primtalen så här:

for i in range(2,n+1):
    if sall[i] == 0:
        print(i)

Om n till exempel är 100, är kodens utskrift följande:

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

---

Uppgift 1 Olöst

Det finns 25 primtal mellan 1...100? Hur många primtal finns det mellan 1...1000?

Skriv ditt program här:

---

Uppgift 2 Olöst

Summan av primtal mellan 1..100 är 1060. Vad är summan av primtal mellan 1...1000?

Skriv ditt program här:

---

Uppgift 3 Olöst

Primtalstvillingar är två primtal vars skillnaden är 2. Följande lista visar alla primtalstvillingar mellan 1...100.

3 5
5 7
11 13
17 19
29 31
41 43
59 61
71 73

Skriv ett program som skriver ut alla primtalstvillingar mellan 1...1000 på motsvarande sätt.

Skriv ditt program här:

---

Uppgift 4 Olöst

När du skriver talet 527227, behöver du följande siffror:

0 0
1 0
2 3
3 0
4 0
5 1
6 0
7 2
8 0
9 0

Du behöver 3 stycken siffra 2, 1 stycke siffra 5, 2 stycken siffra 7 och inga andra siffror.

Skriv ett program som skriver ut en motsvarande statistik när du skriver talet 999⁹⁹⁹.

Skriv ditt program här:

---

Uppgift 5 Olöst

Det finns n spelare i en krets, som har numrerats 1, 2, 3, ..., n medsols. Spelare 1 börjar, och varannan spelare ska elimineras, tills det finns bara en spelare i kretsen.

Om n till exempel är 7, är eliminationsordningen följande:

2
4
6
1
5
3
7

Skriv ett program som skriver ut eliminationsordningen när n är 1000 på motsvarande sätt.

Skriv ditt program här:

---

Uppgift 6 Olöst

Följande lista visar för varje tal mellan 1...10 antalet delare.

1 1
2 2
3 2
4 3
5 2
6 4
7 2
8 4
9 3
10 4

Talet 10 har till exempel 4 delare: 1, 2, 5 och 10.

Skriv ett program som skriver ut en motsvarande statistik för talen 1...1000.

Skriv ditt program här:

---