Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 1
Lekce 6: Test prvočíselnosti- Úvod
- Výzva: test prvočíselnosti
- Postupné dělení
- Co je to počítáčová paměť?
- Efektivita algoritmů
- Úroveň 3: Výzva
- Eratosthenovo síto
- Úroveň 4: Eratosthenovo síto
- Test prvočíselnosti se sítem
- Úroveň 5: Postupné dělení pomocí síta
- Věta o prvočíslech
- Prvočíselná spirála
- Mezery mezi prvočísly
- Kompromis mezi časovou a paměťovou složitostí
- Shrnutí (co bude dál?)
Věta o prvočíslech
Jak můžeme odhadnout počet prvočísel až po x? Tvůrce: Brit Cruise.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.
Transkript
Představte si přirozená čísla
uspořádaná do spirály. Prvočísla jsme obarvili na modro
a složená čísla ponechali černá. Naskýtá se zajímavá otázka: „Kolik je prvočísel
v porovnání se složenými čísly?“ Podívejme se na to
nejdříve z širšího pohledu. Povšimněte si, že barva
prvočísel je hustá uprostřed, směrem ven postupně řídne,
ale nikdy nezmizí docela. Já o tom rád uvažuji takto: Představte si uprostřed
nekonečně vysoký strom. Z něj se na zem snášejí listy
představující prvočísla a na zemi se nepředvídatelným
způsobem usazují: nejhustěji u paty stromu, ale jak se od stromu
vzdalujeme listů ubývá, ačkoliv pořád nějaké potkáváme. A totéž se přesně děje,
když postupujeme k větším číslům. Stále nalézáme další prvočísla, ale jejich počet postupně klesá,
čím dál se od stromu podíváme. Vraťme se k naší otázce: Kolik existuje prvočísel menších
než nějaké přirozené číslo ‚x‘? Když si uděláme tabulku, vidíme,
že počet prvočísel se neustále zvětšuje. Ale jak hledáme dál,
nacházíme jich méně a méně. Pojďme si nakreslit graf
s počtem prvočísel na svislé ose a rozsahem hledání (‚x‘)
na vodorovné ose. Když pohled oddálíme až k miliardám, všimněte si, že se křivka nikdy nenarovná. Pořád roste, i když nepatrně. Zamysleme se nejdříve nad hustotou
prvočísel menších než číslo ‚x‘. Hustotu získáme tak, že vydělíme
počet prvočísel rozsahem hledání (‚x‘). Mezi prvními 100 přirozenými
čísly najdeme 25 prvočísel, čili 25 %. Podobně mezi prvními 10 000 čísly
najdeme 1229 prvočísel, 12,29 % je prvočísel. Mezi prvním milionem čísel
najdeme 7,84 % prvočísel a prvočísel menších
než 100 milionů je 5,76 %. Jak pokračujeme dále,
tato hustota klesá, přestože pomaleji a pomaleji. Tady vidíte graf s rozsahem
hledání na vodorovné ose a hustotou prvočísel na ose svislé. Všimněte si, že při vzdalování prvočísla
tvoří stále menší zastoupení čísel. Překvapivě se tento vztah
vyskytuje i v přírodě. Najdeme ho v galaxiích,
bouřích, květech a dokonce i uvnitř našich těl jako uspořádání nejmenšího odporu známého jako „logaritmická spirála“. Jak se spirála otáčí,
neustále se vzdaluje od středu. Zní to neuvěřitelně, ale rychlost
otáčení logaritmické spirály je svázána s hustotou prvočísel.
A to následovně: Sledujme počet otáček,
které si označíme ‚φ‘ („fí“), a vzdálenost od středu,
tu označme ‚r‘. Když nakreslíme graf závislosti ‚φ‘ na ‚r‘, uvidíme, že je popsán
přirozeným logaritmem. To znamená, že přirozený
logaritmus vzdálenosti má vztah k počtu otáček. Graf přirozeného logaritmu se obvykle
zapisuje pomocí proměnných ‚x‘ a ‚y‘, kde ‚y‘ se rovná přirozenému logaritmu ‚x'
(neboli y = ln x). Za povšimnutí stojí, že graf klesá
podobně zvolna jako hustota prvočísel. Jako poslední krok převrátíme vztah a na svislou osu vyneseme
1/(ln x) místo ‚y‘. A jak oddalujeme pohled,
před očima se nám zjeví stejná křivka, jako když jsme vykreslili hustotu prvočísel. Ověřme si to přiložením
obou grafů k sobě. Zelená křivka znázorňuje y = 1/(ln x), červená hustotu prvočísel menších než ‚x‘. Jak se vzdalujeme,
křivky se přibližují. Když jdeme k větším číslům,
zelená křivka je lepším odhadem červené. Tomu se říká
„asymptotický zákon o rozložení prvočísel“. Dostali jsme rovnici,
která nám přesně řekne, jaká je hustota prvočísel - bez počítání. Hustota prvočísel menších
než přirozené číslo ‚x‘ je přibližně 1/(ln x). Řekněme, že potřebujeme zjistit hustotu
prvočísel mezi 1 a 100 biliony. Hračka. 1/ln(100 000 000 000 000) = 3.1 %. Porovnejme výsledek s opravdu spočítanými prvočísly,
kterých je 3,2 %. To se liší jen o 0,1 %. A jak ověřujeme větší a větší čísla, rozdíl se blíží k nule. Uvědomte si, že můžeme tento
vztah pro hustotu prvočísel použít k odhadu počtu prvočísel
menších než ‚x‘. Počet prvočísel je plocha
pod křivkou hustoty, což lze zjednodušit, pokud
hustotu považujeme za konstatní. Počet prvočísel se rovná
součinu velikosti a hustoty neboli x / (ln x). A to je prvočíselná věta. Zde vidíte modrou křivku
y = x / (ln x) a žlutou křivku, která vyjadřuje
skutečný počet prvočísel. Když graf oddálíme, tyto křivky
se v nekonečnu nakonec spojí v jednu. A to je vše. Máme rovnici,
která nám přibližně předpoví, kolik je prvočísel menších
než nějaká hodnota – a bez počítání. Kupříkladu bychom chtěli vědět,
kolik je prvočísel menších než 100 bilionů. 100 bilionů děleno přirozeným
logaritmem 100 bilionů = 3,1 bilionu. Porovnejme to se skutečným
počtem - 3,2 bilionu. Odpověď je z více než 96,87 procent přesná – dokonce i u takto
relativně malých čísel. Zopakujme si to:
Pokud hledáme až po nějaké číslo ‚x‘, hustota prvočísel činí přibližně 1 / (ln x) A počet prvočísel je přibližně x / ln(x). To je prvočíselná věta.