问题 D: prime
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
对于某个数n,,我们这次的工作仅是求出小于n且和n互质的数的个数,,比如n=10时 1,3,7,9均与10互质，互质的定义是gcd(a,b)=1 。
输入格式
输入只有一行，一个数N（1<=N<=2,000,000,000）。
输出格式
输出也只有一行，输出和小于n且和n互质的数的个数
输入样例 复制
10
输出样例 复制
4
数据范围与提示
欧拉函数： 设φ(n)是比n小的数中与n互质的数的个数。 则对于n的质因数分解n=p1^a1*p2^a2*...*pi^ai （pi为质数），φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pi); φ(n) 即为所求。注意，当n为素数时，φ(n)=n-1