Eratostheneen seula
Eratostheneen seula on kreikkalaisen filosofi Eratostheneksen kehittämä yksinkertainen algoritmi kaikkien alkulukujen löytämiseen äärellisestä lukujoukosta. Se on tehokkain tapa löytää pienet (alle 10 miljoonaa) alkuluvut[1].
Algoritmi[muokkaa | muokkaa wikitekstiä]
Seulan toimintaperiaate (algoritmi) on seuraava:
- Kirjoitetaan lista kaikista luonnollisista luvuista alkaen kakkosesta ja päättyen johonkin valittuun suurimpaan lukuun n.
- Poistetaan listasta kaikki luvun 2 monikerrat (4, 6, 8 jne.).
- Listan seuraava jäljellä oleva luku on alkuluku.
- Poistetaan listasta kaikki ne luvut, jotka ovat sekä edellisessä vaiheessa löydettyä alkulukua suurempia että sen monikertoja.
- Toistetaan vaiheita 3 ja 4, kunnes listan seuraava jäljellä oleva luku on suurempi kuin listan suurimman luvun n neliöjuuri.
- Nyt listassa on jäljellä vain alkulukuja.
Ilman viidennen kohdan rajoitusta algoritmi olisi aikaa vievä suurilla lukujoukoilla. Todistus väitteelle, ettei lukua suurempia kokonaislukuja tarvitse tarkistaa lainkaan on viitteessä.[2]
Esimerkki[muokkaa | muokkaa wikitekstiä]
Kun halutaan tietää kaikki sataa pienemmät alkuluvut, kirjoitetaan listaan luvut 2—100. Aloitetaan pienimmästä luvusta kaksi, joka on alkuluku, ja poistetaan sillä jaolliset luvut 4, 6, 8, ..., 100. Nyt pienin jäljellä oleva luku on kolme, sekin alkuluku, jonka monikerrat 6, 9, 12, ..., 99 poistetaan. Koska neljä on poistettu, se ei ole alkuluku, ja siirrytään viiteen. Kun on poisto-operaatioissa on saavutettu sadan neliöjuuri 10, kaikki muut kuin alkuluvut on poistettu listasta.
Lähteet[muokkaa | muokkaa wikitekstiä]
- ↑ The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.
- ↑ Ratkaisuja ohjaustehtäviin 3 – Tehtävä 3.3. Jyväskylän yliopisto. Viitattu 4.1.2009. [vanhentunut linkki]
