Obeleži sve kategorije koje odgovaraju problemu

Написати програм који за дати природан број $n$ исписује вредност Мертенсове функције $M(n)$.

Мертенсова функција је дефинисана као $M(n) = \sum_{i=1}^n \mu(i)$, где је $\mu(i)$ Мебијусова функција:

$$\mu(i)= \left . \begin{cases} 0 & \text{ако је } i \text{ дељиво квадратом неког броја}\\ 1 & \text{ако је } i \text{ производ парног броја различитих простих бројева}\\ -1 & \text{ако је } i \text{ производ непарног броја различитих простих бројева}\\ \end{cases} \right .$$

Улаз

На стандардном улазу се налази природан број $n$, не већи од милион.

Излаз

На стандардни излаз исписати један цео број, вредност поменуте функције.

Пример

Улаз

10

Излаз

-1

Објашњење

n       1   2   3   4   5   6   7   8   9  10
mi(n)   1  -1  −1   0  −1   1  −1   0   0   1
M(n)    1   0  −1  −1  −2  −1  −2  −2  −2  −1