Složitost, implementace algoritmu

Opakování

• Zopakovali jsme pojmy časové složitosti algoritmu v nejhorším a v průměrném případě. Určili jsme si časovou složitost obou algoritmů z předchozího cvičení.
• Mluvili jsme o tom, že velikost vstupu může být pro různé algoritmy uvažováná různě (hodnota čísla, délka textu, kombinace velikostí více různých vstupů, …). Ukázali jsme si to i na příkladech.

Úkoly

• Pro následující problémy navrhněte algoritmy, které je řeší.
  
• Popište je pseudokódem, určete jejich složitost v nejhorším případě a implementujte je v jazyce C.
  
• Šablona pro řešení v jazyce C.

1. Je dané číslo prvočíslo?
2. Vypsat prvních n prvočísel.
3. Vypsat všechny prvočíslené dělitele daného čísla (pokud se nějaký dělitel opakuje, vypište jej tolikrát, kolikrát je potřeba).