Problem1117--互质

1117: 互质

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

Solved: 21Submit: 28Statistics

Description

给定正整数n,有多少个小于等于n的正整数与n互质,两个数互质的条件为两个数只有1这个共同的因子.

Input

多组测试数据,每组仅一行,为正整数n.(n<=100000)

Output

对于每组数据输出有多少个与n互质的数

Sample Input Copy 

9

Sample Output Copy 

6

Source/Category

 
Submit