OpenJudge

3:EulerPhi函数

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

正整数nphi(n)的值是"小于等于n的数中,与n互质的数的个数”。phi(n)的值也可以用下面公式计算:

phi(n) = n(1-1/p1)(1-1/p2)...(1-1/pm)                           

其中p1,p2...pmn的所有质数约数(既是质数又是n的约数)。

给定n,求phi(n)值。


输入
1个正整数n(1 <= n <= 10000)
输出
一个数,既phi(n)的值
样例输入
#1:
9

#2:
6
样例输出
#1:
10

#2:
4
提示
对于60%的测试点,n <= 100
对于80%的测试点,n <= 1000
对于100%的测试点,n <= 10000

* n本身也是自己的约数,但不一定是质数
* 9有质约数3,phi(9) = 9(1-1/3) = 6
* 10有质约数2、5,phi(10) = 10(1-1/2)(1-1/5) = 4
全局题号
15161
添加于
2017-06-02
提交次数
26
尝试人数
16
通过人数
15