BEZKW

Bez kwadratów

Problem code: BEZKW | Time: 1.00 s | Memory: 8 MB | Solved: yes | print

Liczbę naturalną nazwiemy bezkwadratową, gdy żaden jej dzielnik większy od 1 nie jest kwadratem liczby naturalnej. Dana jest liczba n. Ile jest liczb bezkwadratowych nie większych niż n?

Wejście

Liczba naturalna n (1 ≤ n ≤ 500 000)

Wyjście

Jedna liczba całkowita - ilość liczb bezkwadratowych nie większych niż n.

Przykład

Dla danej

5 poprawnym wynikiem jest liczba

4
gdyż liczby 1, 2, 3, 5 są bezkwadratowe.