Eratosthenes a jeho sito
Nie je číslo ako číslo. A podľa toho, ako sa na čísla dívame, môžeme ich všelijako preosievať, aby nám ostali nakoniec len tie naše obľúbené.
To by tak bolo, keby sme mali preosievač, ktorý by dokázal vytriediť čísla, čo budú vyžrebované v nasledujúcom ťahu Lota :-)
Také sito ale nemáme a tak sa musíme tešiť z toho, čo ide a čo nám zanechali premýšľajuci predkovia. Napr. ujo Eratosthenes, ktorý sa na iný svet pobral okolo roku 195 pred narodením Ježiša. Asi mu bolo pridlho čakať...
Jeho sito je alergické na čísla, čo sa dajú niečim narovno podeliť a pritom každému ostane viac, ako jedno čosi a menej, ako všetko. Napr. šesť žuvačiek možno takto rozdeliť medzi dvoch či troch žuvateľov. A také číslo $24$ sa ide rozkrájať od snahy deliť sa - na $2,3,4,6,8,12$ častí ho možno rozkúskovať.
Na opačnom brehu stoja čísla, čo sa nijakovsky rozdeliť nedajú. Kdeže tam pre nich bratstvo, rovnosť a sloboda! Jeden dostane všetko, ostatní nič. Alebo vždy niekto má menej a niekto viac... Aj to vychytené šťastné číslo $7$ je také - egoistické. Hovoríme tak číslam, čo sa nedajú rozdeliť na viac rovnakých častí, aby sa každému viac ako jedna odrobinka dostala.
V matematike však neslobodno hanlivé slová používať, a preto tie čísla, čo sa nedajú deliť ničím, väčším ako jedna a menším, ako oni samy, nazývame prvočísla (v angličtine prime numbers, alebo krátko, primes). Tuhľa sú všetky prvočísla do 100 (je ich $25$, ak by ste chceli ich počet)
$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.$
Prečo ten názov, prvočísla? Pretože ich môžeme chápať ako stavebné tehličky, z ktorých sa dá vyskladať ľubovoľné celé číslo - ich násobením. Napr. to veľmi deliteľné číslo $24$ môžeme napísať ako $3 . 2 . 2 . 2$, alebo $3 . 2^3$. Samozrejme, že ho môžeme písať aj inak, napr. ako súčin $3 . 8$, alebo $6 . 4$. No pokiaľ sú v tom súčine čísla, čo ešte nie sú prvočísla, delíme ich kým sa to dá a nakoniec musíme dôjsť k súčinu, ktorého všetky členy sú prvočísla. Teda, každé číslo môžeme rozložiť na súčin prvočísel.
Keby sme mali záujem o väčšie prvočísla, povedzme do 10000, to by sa nám už ťažšie robilo len tak, priamymi pokusmi o delenie. Eratosthenes vymyslel zaujímavý spôsob, ako preosiať všetky čísla, až po nejaké dané (veľké) $n$ tak, aby ostali len prvočísla. To je to Eratosthenovo sito.
Sito funguje takto.
- Napíšeme si nádejné prvočísla, na začiatku to budú všetky císla $2,3,4,\dots,n-1,n$. Z nich budeme postupne vyčiarkovať tie, čo určite nemôžu byť prvočíslami, lebo sú násobkami nejakého prvočísla.
- Prvé nevyčiarknuté číslo, volajme ho $p$, je určite prvočíslo. Vyčiarkneme všetky čísla, ktoré sú jeho násobkami (aspoň dvojnásobok treba). Napr. na začiatku je $p=2$ a vyčiarkneme všetky párne čísla.
- Krok 2 opakujeme, kým je čo vyčiarkovať. Keď skončíme, ostanú nám len prvočísla.
Pekná ilustrácia toho, ako sa čísla riedia je na stránke Cut the Knot (Pretni uzol :-) Len musíte ísť na spodok stránky a tam klikať na čísla pod tabuľkou (to sú tie naše prvé nevyčiarknuté čísla - preto to začína dvojkou).
Samozrejme, pre veľké hodnoty $n$ je lepšie, keď to vyčiarkávanie za nás urobí počítač. Tuhľa je program - funkcia v programovacom jazyku Python, ktorej keď predhodíme číslo $n$, vráti nám všetky prvočísla až poňho.
from math import sqrt def ersito(n): sito = [True] * (n+1) sito[:2] = [False, False] for k in range(2, int(sqrt(n))): if sito[k]: m = n/k - k sito[k*k::k] = [False] * (m+1) prvoc = [i for i in range(n+1) if sito[i]] return prvoc
Čo ten program robí? Myslíme si, že aj tým, čo Python neveľmi poznajú, povedia niečo naše objasnenia k programu. Sú tam dve vylepšenia oproti tomu, čo sme hovorili hore.
- Vyčiarkujeme len násobky prvočísel, ktoré sú menšie, alebo rovnaké ako $\sqrt{n}$. To stačí, lebo každé zložené číslo (tak nazývame ne-prvočíslo) sa dá napísať ako súčin dvoch čísel, z ktorých to menšie, je prvočíslo, neprevyšujúce $\sqrt{n}$. Napr. $10=2 . 5, 121=11 . 11$. Teda stačí, ak to zložené číslo vyčiarkneme, ako násobok toho menšieho prvočísla. Tým sa strašne veľa výpočtového času ušetrí.
- Ak už sme pri nejakom prvočísle $p$, ktorého násobky vyčiarkujeme, nemusíme začínať od $2p$ ale od $p^2=p . p$. Skutočne, všetky tie násobky od $2 p$ po $(p-1)p$ sme už museli vyčiarknúť ako násobky prvočísel, menších ako $p$. Napríklad pre $p=11$ sme vyčiarkli už predtým čísla $$ 2 . 11, 3 . 11, 4 . 11 = 2 . 22, 5 . 11, 6 . 11 = 3 . 22, 7 . 11, 8 . 11= 2 . 44, 9 . 11= 3 . 33, 10 . 11 = 5 . 22. $$
K samotnému programu. Na riadku č. 1 si importujeme funkciu sqrt na výpočet druhej odmocniny. Riadok 3 je definícia funkcie, ktorej meno je ersito a ktorej vstupom je nejaké prirodzené číslo $n$. Nekontrolujeme to, ale veď používateľ je inteligentný :-)
Ďalej nasleduje to, ako tá funkcia počíta prvočísla podľa Eratosthena. Riadok 4 - vytvoríme zoznam sito, ktorý nám hovorí, že čísla s poradím $0,1,2,\dots, n$ sú nevyčiarknuté. To, že pre nás "existujú", si vyznačíme pravdivostnou hodnotou True. Vyčiarknutým číslam budeme dávať hodnotu False. Na riadku 5 sme vyčiarkli prvé dve čísla, teda nulu a jedničku, bo to prvočísla nie sú.
Riadky 6-9 realizujú to vyčiarkovanie násobkov prvočísel, počnúc dvojkou a končiac prirodzeným (int = integer) číslom, ktoré je najbližšie zdola ku odmocnine z $n$. Ideme po všetkých číslach $k$ z tohoto rozsahu, ale vyčiarkujeme násobky len pre nevyčiarknuté čísla - to je podmienka v riadku 7. Číslo $m$ na riadku 8 je počet násobkov čísla $k$, nie väčších ako $n$, ale začiname násobkom $k . k$, ako sme to zdôvodnili v bode 2 povyššie. Na riadku 9 všetky tie násobky jedným šmahom vyčiarkneme, teda priradíme im toľko hodnôt False, koľko treba.
Po skončenom vyčiarkovaní, na riadku 10 z celého zoznamu sito vyberieme len nevyčiarknuté čísla a tie vrátime ako výsledok výpočtu funkcie ersito. To budú tie prvočísla, ktoré sme chceli.
Príklad na hranie sa s funkciou ersito, v IPythone (pre tých, čo vedia, o čom je reč, alebo sú zvedaví :-)
In [1]: P=ersito(1000000) # prvočísla do milión In [2]: sum(P) # ich súčet Out[2]: 37550402023 In [3]: len(P) # ich počet Out[3]: 78498 In [4]: P[1001] # tisíce prvočíslo Out[4]: 7933 # počítať sa začína od nuly # Koniec? :-)