[Etusivu] [Opiskelutehtäviä 1 2 3 4 5 6 7 8]


Tehtävä 3.2. Määrää kaikki satasta pienemmät alkuluvut.

Ratkaisu

Käytetään apuna Eratostheneen seulaa 6−sarakkeisen taulukon muodossa (ks. kurssikirjan s. 29).

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 (itseään pienemmällä) alkuluvulla. Jos nyt ykkönen olisi alkuluku, ei muita alkulukuja olisi ollenkaan!

Kakkonen on ensimmäinen alkuluku. Sen jälkeen taulukon luvuista yliviivataan kaikki kahdella jaolliset luvut. Luku 3 on seuraava alkuluku, koska se ei ole kahdella jaollinen. Yliviivataan kolmella jaolliset luvut (jotka eivät ole jo yliviivattu). Ensimmäinen yliviivaamaton on seuraava alkuluku. Näin jatketaan.

Poistettavien lukujen eli alkulukujen monikertojen yliviivaaminen voidaan lopettaa lukua 11 pienempien 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. Esimerkiksi. ja sillä on siis tekijänä ainakin kolmonen.

Näin ollen lukua 100 pienemmät alkuluvut ovat edellä ympyröidyt 2, 3, 5, ..., 97.

Huomautus. Alkulukuja seulalla etsittäessä riittää siis poistaa seulan ylärajan neliöjuurta pienempien alkulukujen monikerrat, jolloin seulaan jää jäljelle kyseisessä lukualueessa esiintyvät alkuluvut.

Lisätietoja. 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 kuitenkin 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.

 

• 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äviä 3]