• 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:

vstup = input()

slova = []

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

    # moznost 1: scitani seznamu
    # slova = slova + rozdeleny_vstup

    # moznost 2: for cyklus a append
    for slovo in rozdeleny_vstup:
        slova.append(slovo)

    vstup = input()

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.