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.
Seulan toimintaperiaate (algoritmi) on seuraava:
Ilman viidennen kohdan rajoitusta algoritmi olisi aikaa vievä suurilla lukujoukoilla. Todistus väitteelle, ettei lukua suurempia kokonaislukuja tarvitse tarkistaa lainkaan on viitteessä.
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.
This article uses material from the Wikipedia Suomi article Eratostheneen seula, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Sisältö on käytettävissä lisenssillä CC BY-SA 4.0, ellei toisin mainita. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Suomi (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.