Мертенсова функција
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 0,1 s | 64 Mb | standardni izlaz | standardni ulaz |
Написати програм који за дати природан број \(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
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.