Problem1727--互素

1727: 互素

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 0Submit: 555Statistics

Description

求小于n且与n互素的整数个数。

Input

整数n，n<=109

Output

 互素的整数个数

Sample Input Copy 

18

Sample Output Copy 

6

HINT

欧拉函数

Source/Category

 
Submit