1491: 互质个数

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：20 Solved：2

Description

对于某个自然数n，出小于n且和n互质的数的个数。比如n=10时 1,3,7,9均与10互质。互质的定义是gcd(a,b)=1（a,b最大公约数为1）。n的数据范围（1<=n<=3*108）。

Input

输入n的值。

Output

输出符合题意的互质个数。

Sample Input Copy 

10

Sample Output Copy 

4

Source/Category

SubmitSubmit RecordStatisticsShowOff!