Eratostheneen seula

Wikipediasta
Siirry navigaatioon Siirry hakuun
Eratostheneen seula tietokoneanimaationa. Animaatiossa seulaa sovelletaan kaikkien välillä [2,120] olevien alkulukujen löytämiseen. Aluksi todetaan, että luku 2 on alkuluku ja poistetaan kaikki kakkosen monikerrat, koska ne ovat kaikki jaollisia kahdella. Tämän jälkeen ensimmäinen jäljellä oleva luku, 3, on alkuluku ja poistetaan kaikki luvun 3 monikerrat. Näin jatketaan, kunnes taulukon seuraava jäljellä oleva luku on 11. Tällöin seula on täydellinen, koska 11 on suurempi kuin luvun 120 neliöjuuri. Nyt kaikki jäljellä olevat taulukon luvut ovat alkulukuja.

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].

Seulan toimintaperiaate (algoritmi) on seuraava:

  1. Kirjoitetaan lista kaikista luonnollisista luvuista alkaen kakkosesta ja päättyen johonkin valittuun suurimpaan lukuun n.
  2. Poistetaan listasta kaikki luvun 2 monikerrat (4, 6, 8 jne.).
  3. Listan seuraava jäljellä oleva luku on alkuluku.
  4. Poistetaan listasta kaikki ne luvut, jotka ovat sekä edellisessä vaiheessa löydettyä alkulukua suurempia että sen monikertoja.
  5. Toistetaan vaiheita 3 ja 4, kunnes listan seuraava jäljellä oleva luku on suurempi kuin listan suurimman luvun n neliöjuuri.
  6. Nyt listassa on jäljellä vain alkulukuja.

Viidennen kohdan rajoitus lyhentää algoritmin suoritusaikaa suuresti varsinkin suurilla n:n arvoilla. Käsittely voidaan lopettaa jo tässä vaiheessa, koska jokainen luonnollinen luku m, joka ei ole alkuluku, voidaan esittää kahden luonnollisen a ja b tulona: m = a · b, joista kumpikaan ei ole 1 eikä m. Jos tässä ab, on joko ja . Näin ollen jokaisella luvulla m < n, joka ei ole alkuluku, on ainakin yksi tekijä, joka on pienempi kuin , ja näin ollen jokainen tällainen luku on tähän kohtaan saavuttaessa jo käsitelty. [2]

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.

  1. The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.
  2. The Sieve of Eratosthenes nickymeuleman.netlify.app. Viitattu 6.6.2024.

Aiheesta muualla

[muokkaa | muokkaa wikitekstiä]