Se citeste un numar natural n. Un numar este liber de patrate daca nu se divide cu niciun patrat perfect mai mare decat 1 (adica niciun factor prim al sau nu apare la puterea a doua sau mai mare). Folosind o varianta a ciurului lui Eratostene, determinati cate numere din intervalul [1, n] sunt libere de patrate.
- Date de intrare
- Pe prima linie se afla numarul natural n.
- Date de iesire
- Afiseaza un singur numar natural: cate numere din [1, n] sunt libere de patrate.
- Restrictii
- 1 <= n <= 100000
Exemple
Exemplul 1
Intrare
10
Iesire
7
Exemplul 2
Intrare
1
Iesire
1