• Lekce 6
  • Úlohy
    • Eratosthenovo síto
  • Co jsme dnes probrali
    • Šikovné funkce pro pole
    • Vstup
    • Eratosthenovo sito

Lekce 6

Úlohy

Eratosthenovo síto

Zkuste si naimplementovat algoritmus pro hledání prvočísel, který jsme popsali na hodině.

Co jsme dnes probrali

Šikovné funkce pro pole

• sum(pole) - Vrátí součet všech čísel v poli
• min(pole) - Vrátí nejmenší číslo v poli
• max(pole) - Vrátí největší číslo v poli
• len(pole) - Vrátí počet prvků v poli

Vstup

• Doteď jsme používali input() pro načtení vstupu, načítali jsme jen jednu hodnotu
• Co když chceme načíst více hodnot?
• Každý měl za úkol napsat program, který načte neznámý počet řádků, pokud narazí na prázdný řádek, přestane načítat a vypíše slova v řádcích (uložená do pole).
• Řešení může vypadat třeba takto:

1
vstup = input()
2

3
slova = []
4

5
while vstup != "":
6
    # pole slov z toho radku
7
    rozdeleny_vstup = vstup.split()
8

9
    # moznost 1: scitani seznamu
10
    # slova = slova + rozdeleny_vstup
11

12
    # moznost 2: for cyklus a append
13
    for slovo in rozdeleny_vstup:
14
        slova.append(slovo)
15

16
    vstup = input()
17

18
print(slova)

Eratosthenovo sito

• Rychlý algoritmus na nalezení prvočísel od 1 do $n$.
  • Má skorolineární časovou složitost $\mathcal{O}(n\log{\log{n}})$
• Postupně vyškrtáváme násobky čísel, tím nám zbydou pouze prvočísla.
• Více informací o algoritmu najdete zde a zde.