Ero sivun ”Eratostheneen seula” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Käyttäjän 213.255.161.130 (keskustelu) muokkaukset kumottiin ja sivu palautettiin viimeisimpään käyttäjän QWerk tekemään versioon. |
|||
Rivi 4:
== Algoritmi ==
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 <math>\scriptstyle \sqrt{n}</math> suurempia kokonaislukuja tarvitse tarkistaa lainkaan on viitteessä.<ref>{{Verkkoviite | Osoite = http://www.math.jyu.fi/matappro/mappro3/ohjaus/_ratkaisuja_kesa08/ohjaus_3/ | Nimeke = Ratkaisuja ohjaustehtäviin 3 – Tehtävä 3.3. | Julkaisija =Jyliopisto | Viitattu = 4.1.2009}}</ref>
== Esimerkki ==
| |||