Eratostheneen seula
Wikipedia
Eratostheneen seula on kreikkalaisen filosofi Eratostheneksen kehittämä yksinkertainen algoritmi alkulukujen löytämiseen äärellisestä lukujoukosta, ja se toimii suhteellisen hyvin, kun lukujoukko on pieni. Seuraavassa seulan käyttöohje:
- Kirjoitetaan lista kaikista ykköstä suuremmista luonnollisista luvuista lukuun n asti.
- Listan ensimmäinen luku on 2. Poistetaan listasta kaikki luvun 2 monikerrat 4, 6, 8 jne.
- Listan seuraava jäljellä oleva luku on 3. Poistetaan kaikki luvun 3 monikerrat 6, 9, 12 jne.
- Seuraava jäljellä oleva luku on 5. Poistetaan kaikki luvun 5 monikerrat 10, 15, 20 jne.
- Näin jatketaan, kunnes listan seuraavan jäljellä olevan luvun neliö on suurempi kuin seulan suurin luku n, ts. luvun n neliöjuureen asti.
- Nyt vain alkuluvut ovat jäljellä.
Kun halutaan tietää esimerkiksi kaikki sataa pienemmät alkuluvut, kirjoitetaan läpi luvut 2—100. Aloitetaan pienimmästä luvusta kaksi, joka on siis 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 saavutettu sadan neliöjuuri 10, on kaikki muut kuin alkuluvut poistettu listasta 2—100.
[muokkaa] Aiheesta muualla
- Interaktiivinen animaatio (vaatii JavaScriptin käyttöä)
