Ојлерова функција
vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,1 s | 64 Mb | standardni izlaz | standardni ulaz |
Напиши програм који одређује колико има природних бројева \(m\) мањих или једнаких од датог броја \(n\) који су узајамно прости са \(n\) тј. за које је \(1 \leq m \leq n\) и \(nzd(m, n) = 1\).
Улаз
Са стандардног улаза уноси се број \(n\) (\(1 \leq n \leq 2\cdot 10^9\)).
Излаз
На стандардни излаз исписати само тражени број.
Пример
Улаз
9
Излаз
6
Објашњење
Бројеви узајамно прости са бројем \(n\) су бројеви 1, 2, 4, 5, 7 и 8 и има их укупно 6.
Пример 2
Улаз
1
Излаз
1
Објашњење
Број 1 задовољава услове \(1 \leq 1\) и \(nzd(1, 1) = 1\).
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.