Module: 欧拉函数和数论中的其他问题

Problem

1 /9

给定一个自然数

$n <= 10^9,$ 求小于 \的自然数个数(n\ ) 与

$n$ 互质。这个数字用

$f(n)$ 表示，称为 Euler 的 phi 函数。算法的复杂度应该是

$O(\sqrt{n})$ .

输入
输入是一个自然数n。

印记
打印问题的答案。

<头> <正文>

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

​x
 
​

#	输入	输出
1	2	1