Ohjelmoinnin alkeet

Luku 14: Eratostheneen seula

Alkuluku on kokonaisluku, joka on vähintään 2 ja jaollinen vain 1:llä ja itsellään. Esimerkiksi luvut 5, 11 ja 29 ovat alkulukuja. Luku 12 puolestaan ei ole alkuluku, koska 3*4 = 12.

Tämän luvun tavoitteemme on tehdä ohjelma, joka etsii alkulukuja. Käytämme tähän algoritmia, joka tunnetaan nimellä Eratostheneen seula. Se etsii kaikki alkuluvut, jotka ovat välillä 2...n, missä n on haluttu yläraja.

Seulan toiminta

Eratostheneen seula pitää yllä kirjanpitoa, jossa on luvut 2...n. Algoritmi käy läpi luvut pienimmästä suurimpaan. Jokaisen luvun i kohdalla algoritmi merkitsee rastin luvun moninkertojen 2*i, 3*i, 4*i jne. kohdalle. Rasti tarkoittaa, että kyseinen luku ei ole alkuluku, koska se on jaollinen luvulla i. Kun algoritmi päättyy, alkuluvut tunnistaa siitä, että niiden kohdalla ei ole rastia.

Tarkastellaan esimerkkinä Eratostheneen seulan toimintaa, kun n on 100. Tällöin algoritmi etsii kaikki alkuluvut, jotka ovat välillä 2...100. Tässä on algoritmin aloitustilanne:

Algoritmi rastittaa ensin luvun 2 moninkerrat 4, 6, 8, jne.:

Sitten algoritmi rastittaa luvun 3 moninkerrat 6, 9, 12, jne.:

Algoritmi jatkaa vastaavalla tavalla eteenpäin, kunnes se on käynyt läpi kaikki välin 2...100 luvut. Tällöin kirjanpidon sisältö on seuraava:

Tämä tarkoittaa, että alkuluvut välillä 2...100 ovat:

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

Seulan toteutus

Jotta voimme ohjelmoida Eratostheneen seulan, tarvitsemme keinon pitää muistissa lukujen kirjanpitoa. Hyvä tapa tähän on luoda lista, jossa on kohta jokaiselle kirjanpidon luvulle. Voimme luoda listan näin:

seula = [0]*(n+1)

Tämän listan kohdat on numeroitu 0, 1, 2, ..., n, ja jokaisessa kohdassa on aluksi luku 0. Ideana on, että kohdassa seula[x] on tieto, onko luku x rastitettu. Arvo 0 tarkoittaa, että lukua ei ole rastitettu, ja arvo 1 tarkoittaa, että luku on rastitettu. Huomaa, että emme käytä listan kohtia 0 ja 1 algoritmin aikana, koska tarvitsemme kirjanpitoa vasta kohdasta 2 alkaen.

Seuraava koodi toteuttaa Eratostheneen seulan:

n = 100
seula = [0]*(n+1)
for i in range(2,n+1):
    for j in range(2*i,n+1,i):
        seula[j] = 1

Koodin pääsilmukka käy läpi luvut 2...n, ja kunkin luvun i kohdalla sisäsilmukka merkitsee, että luvun moninkerrat 2*i, 3*i, 4*i, jne. eivät ole alkulukuja.

Tämän jälkeen voimme tulostaa löytyneet alkuluvut näin:

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

Esimerkiksi kun n on 100, koodin tulostus on seuraava:

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

---

Tehtävä 1 Ratkaisematon

Välillä 1...100 on 25 alkulukua. Montako alkulukua on välillä 1...1000?

Kirjoita ohjelma tähän:

---

Tehtävä 2 Ratkaisematon

Välin 1...100 alkulukujen summa on 1060. Mikä on välin 1...1000 alkulukujen summa?

Kirjoita ohjelma tähän:

---

Tehtävä 3 Ratkaisematon

Alkulukupari muodostuu kahdesta alkuluvusta, joiden ero on 2. Välillä 1...100 on seuraavat alkulukuparit:

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

Tee ohjelma, joka tulostaa vastaavalla tavalla välin 1...1000 alkulukuparit.

Kirjoita ohjelma tähän:

---

Tehtävä 4 Ratkaisematon

Kun kirjoitat luvun 527227, tarvitset siihen eri numeroita seuraavasti:

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

Esimerkiksi kolmannella rivillä lukee 2 3, koska tarvitset 3 kappaletta numeroa 2.

Tee ohjelma, joka tulostaa vastaavan tilaston, kun kirjoitat luvun 999⁹⁹⁹.

Kirjoita ohjelma tähän:

---

Tehtävä 5 Ratkaisematon

Piirissä on n pelaajaa, jotka on numeroitu myötäpäivään 1, 2, 3, ..., n. Vuoro kiertää piirissä pelaajasta 1 alkaen myötäpäivään ja joka toinen pelaaja poistuu piiristä, kunnes piiri on tyhjä.

Esimerkiksi kun n on 7, pelaajat poistuvat seuraavassa järjestyksessä:

2
4
6
1
5
3
7

Tee ohjelma, joka tulostaa vastaavalla tavalla, missä järjestyksessä pelaajat poistuvat, kun n on 1000.

Kirjoita ohjelma tähän:

---

Tehtävä 6 Ratkaisematon

Seuraava lista näyttää luvuista 1...10, montako jakajaa niillä on:

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

Esimerkiksi viimeinen rivi on 10 4, koska luvulla 10 on 4 jakajaa: 1, 2, 5 ja 10.

Tee ohjelma, joka tulostaa vastaavan tilaston luvuille 1...1000.

Kirjoita ohjelma tähän:

---