Test prvočíselnosti se sítem

Pro rekapitulaci, zkoušíme, jestli číslo 'n' je prvočíslem, pomocí postupného dělení. Tady je odmocnina z 'n'. A tady je 3. Začínáme na 3 a skáčeme dál po 2 až do odmocniny z 'n', a v každém bodě po cestě zkoušíme, jestli ono číslo dělí 'n'. Doteď se lidé snažili snížit počet nutných kroků například pozdějším začátkem a větším krokem. Tady se zastavme a zamysleme se nad ideálním případem pro algoritmus postupného dělení. Co je nejlepší věc, kterou lze udělat, když budeme kroky dělat chytře? Vzpomeňte si, že každé 'n' má prvočíselný rozklad. Řekněme, že odmocnina z 'n' je tady. Vlastně stačí jít jen po prvočíslech. To by bylo nejlepší řešení, protože víme, že když projdeme pouze prvočísla nakonec najdeme prvočíselného dělitele, pokud je 'n' složené. Otázka je, jak je tato metoda efektivní, protože se zdá, že máme perfektní řešení. Napíšeme nový algoritmus, který v prvním kroku zavolá funkci "síto".... ...tento algoritmus zjišťuje, zda je 'n' prvočíslo.... Nejprve zavolá "síto", které vygeneruje dlouhý seznam prvočísel. Pak použije metodu postupného dělení, která využije tento seznam, takže skáčeme pouze po prvočíslech až do odmocniny z 'n'. Ale co je na tom špatně? Můžeme si zobrazit časovou složitost nebo počet potřebných kroků. Vzpomeňte si, že jsem tento algoritmus naprogramoval a teď vložím do každého cyklu počítač kroků. Step++ (krok++) znamená step + 1. Uvnitř tohoto cyklu je také počítadlo kroků step++ Tohle jsou všechno jednotkové operace - zkoumání podmínky a označování. Takže máme počítadlo kroků v každém cyklu. Tady máme porovnání. Vlevo je naše stará metoda postupným dělením, uprostřed je algoritmus, který volá "síto" pro nalezení prvočísel až po 'n', a vpravo je náš návrh, který zavolá síto pro nalezení prvočísel až do odmocniny z 'n', a poté s nimi použije metodu postupného dělení. Podívejme se, co se stane pro malé vstupní hodnoty. Jak vidíme, síto dělá mnoho kroků, takže i naše modifikovaná verze vpravo je pomalejší než postupné dělení. Jak vstupní hodnoty rostou, počet kroků v sítu roste ještě více. Tak zapomeňme na prostředek a srovnejme postupné dělení s naší metodou síta v kombinaci s postupným dělením. Vidíme, že stará metoda postupného dělení je mnohem efektivnější. počet kroků v našem sítu v kombinaci s postupným dělením roste daleko rychleji. Takže to vlastně není zlepšení. Dole je program, který jsem použil na tohle porovnání. Je tam i záznam, který vysvětluje, jak jsem to nastavil. Ale možná si teď říkáte, co kdybychom si prvočísla předpočítali? První krok by bylo sestavení pole prvočísel a uložení na pevný disk. Pak by náš algoritmus jenom postupně dělil a věděl by, jak postupovat pouze po prvočíslech, protože by je program četl z předpočítaného seznamu. Naše pole by třeba obsahovalo prvočísla až s 20 nebo 100 číslicemi. Proč to nemůžeme udělat? Problémem je paměťové omezení. V dalším videu si ukážeme, jak spočítat počet prvočísel. Teď si to ukažme jen na příkladu. Zjistíme, že 5 je prvočíslo. Napíšeme 5 na papír a vložíme jej do kartotéky. Pak najdeme 7 a taky to uložíme. a pak 9.... tedy 11, pardon. Teď máme kartotéku plnou prvočísel. Tohle je naše pole prvočísel. Jak velká by tato kartotéka musela být, pokud bychom chtěli uložit prvočísla s 20 nebo až 100 číslicemi? Můžeme tohle pole vůbec uložit na pevný disk? Pro pochopení toho, proč to není možné, se musíme více zamyslet, jak tohle pole prvočísel roste a jaké jsou omezení dnešních i budoucích počítačů.