OpenJudge

5:欧拉Phi函数

总时间限制:
1000ms
内存限制:
65536kB
描述

在数论中,对于正整数n,函数phi(n)的值是"小于等于n的数中,与n互质的数的个数”。

也可以用下面公式计算:phi(n)=n×(1-1/p1)×(1-1/p2)...×(1-1/pm),其中p1,p2...pm为n的所有质因数(即又是质数又是n的因数)。

输入
一个正整数n,n<=10^7
输出
一个整数,既phi(n)的值
样例输入
45
样例输出
24
提示
45有质因数3和5,那么phi(45)=45(1-1/3)(1-1/5)=24
n本身也是自己的因数,但不一定是质数
全局题号
12716
添加于
2017-03-13
提交次数
22
尝试人数
6
通过人数
6