---
# System prepended metadata

title: Domácí úkol 4.5

---

# Domácí úkol 4.5
## erat3
Počítač dokáže celkem rychle vypsat všechna přirozená čísla do milionu, nahradit nulou čísla dělitelná čísly v zadání a nakonec spočítat počet všech nenulových prvků. "Na papíře" se dá úloha řešit takto:
Je jednodušší počítat, kolik čísel vyškrtáme (výsledek je pak zbytek do milionu.)
Počet vyškrtaných násobků jednoho čísla je roven podílu milionu a daného čísla (podíl zaokrouhlen dolů). Pokud budeme řešit tou nejméně efektivnější metodou, tím vyškrtáme i společné násobky různých čísel, proto musíme požít pravidlo inkluze a exkluze; od násobků samostatných čísel odečteme společné násobky (což jsou čísla dělitelná nejmenším společným násobkem) dvou čísel, přičteme SN tří čísel a odečteme SN čtyř čísel.
Jelikož $154 = 2*77$, nemusíme toto číslo uvažovat.

Jednotlivá čísla:
- $77 \rightarrow 12987$
- $91 \rightarrow 10989$
- $143 \rightarrow 6993$
Společné násobky dvou čísel:
- $n(77,91) = 1001 \rightarrow 999$
- $n(77,143) = 1001 \rightarrow 999$
- $n(91,143) = 1001 \rightarrow 999$
Společné násobky tří čísel:
- $n(77,91,143) = 1001 \rightarrow 999$
Jak je vidět, různá čísla mají nejmenší společný násobek, ale to našemu řešení nijak nevadí.

Nyní podle pravidla inkluze a exkluze spočítáme:
$(12987+10989+6993) - (999+999+999) + (999) = 28971$.

To je počet vyškrtaných čísel, a tak nevyškrtaných zbývá $1 000 000-28 971 = 971029$ (což se shoduje i s programem, takže řešení by mělo být správné).