Prosti brojevi
Koliko ima prostih brojeva od 1 do N?
- Ulaz
Jedan prirodni broj N.
- Izlaz
Broj prostih brojeva koji nisu veći od N.
- Ograničenja
1 ≤ N ≤ 50 000
Primjer 1
Ulaz
20
Izlaz
8
Zapeo si?
Prvo pokušaj sam. Savjeti se otvaraju jedan po jedan, svaki otkriva malo više.
Za svaki broj do N provjeri je li prost, kao u lekciji 11, i broji ih.
Ako je program prespor, pogledaj koliko daleko provjeravaš djelitelje.