Tehtävän 19 ratkaisu

Käytetään apuna Eratostheneen seulaa. Tässä on esitetty 6-sarakkeinen seula, mutta jokseenkin samaan tyyliin voitaisiin käyttää esimerkiksi 10- tai 12-sarakkeista seulaa. Kymmensarakkeinen seula on näistä kolmesta huonoin, sillä siinä saadaan vähiten lukuja "yliviivattua" suoraan.

Kuusi- ja 12-sarakkeisissa seuloissa saadaan pystysuoraan yliviivattua kaikki kakkosen ja kolmosen monikerrat sekä tämän lisäksi oikealta vasemmalle laskevilla viivoilla kaikki viitosen monikerrat ja vasemmalta oikealle laskevilla viivoilla kaikki seiskan monikerrat. Kuusi- ja 12-sarakkeinen seula ovat lähes yhtä hyviä, erotuksena se, että kuusisarakkeinen on hiukan selkeämpi ja järjestelmällisempi viitosen ja seiskan monikertojen yliviivauksessa. Kokeile niin huomaat mitä tällä tarkoitetaan!

Ykköstä ei mielletä alkuluvuksi, sillä jos näin tehtäisiin, ei muita alkulukuja tavallaan olisi olemassa ollenkaan. Näin on, sillä ykkönen jakaa kaikki kokonaisluvut, mutta alkuluvut ovat sellaisia etteivät ne ole jaollisia millään muulla (itseään pienemmällä) alkuluvulla. Jos nyt ykkönen olisi alkuluku, ei muita alkulukuja olisi ollenkaan!

Lukua 100 pienemmät alkuluvut ovat edellä ympyröidyt 2, 3, 5, …, 97.

Lisätietoja. Tässä tapauksessa poistettavien lukujen eli alkulukujen monikertojen etsiminen voidaan lopettaa lukua 11 pienempiin alkulukujen monikertoihin. Näin siksi, että pienin yhdistetty luku, jolla ei ole tekijänä alkulukuja 2, 3, 5, tai 7, on luku , mikä on jo suurempi kuin tässä tarkasteltavan lukualueen yläraja 100.

Esimerkki. ja sillä on siis tekijänä ainakin kolmonen. Alkulukuja seulalla etsittäessä riittää siis etsiä seulan ylärajan neliöjuurta pienempien alkulukujen monikerrat ja poistaa ne, jolloin seulaan jää jäljelle kyseisessä lukualueessa esiintyvät alkuluvut.

Linkkejä:

The sieve of Eratosthene: http://tunes.org/HLL/examples/sieve.html

The sieve of Eratosthene: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Java applet for the sieve: http://www.cut-the-knot.org/Curriculum/Arithmetic/Eratosthenes.shtml

Eratosthenes' sieve (JavaScript): http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm

[Opiskelutehtävä 19] [Vinkki tehtävään 19]

[Ylempi pääsivu] [Edellinen sivu] [Seuraava sivu]