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?)
Test prvočíselnosti se sítem
Použití postupného dělení s pomocí Erastothenova síta Tvůrce: Brit Cruise.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.
Transkript
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čů.