4695: 互素
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：75
通过：32
题目描述
对于某个数n,,我们这次的工作仅是求出小于n且和n互质的数的个数,,比如n=10时 1,3,7,9均与10互质
//互质的定义是gcd(a,b)=1
//互质的定义是gcd(a,b)=1
输入格式
输入只有一行，一个数N（1<=N<=2,000,000,000）。
输出格式
输出也只有一行，输出和小于n且和n互质的数的个数
输入样例 复制
10输出样例 复制
4数据范围与提示
欧拉函数的定义
定义
φ(n) 表示 1~n 中 与 x 互质的数的个数.
pi即为n的质因子.
性质
若 n = p^k ,其中p为质数,那么φ(n)=p^k-p^(k-1) (定义推出)
它在整数n上的值等于对n进行素因子分解后，所有的素数幂上的欧拉函数之积 (定义推出)
欧拉函数是积性函数当 gcd(a,b)=1 时, φ(a*b) = φ(a)*φ(b) , 特别的 , 当 n 为奇数时,φ(2n) = φ(n)
(记得用我哟~）
