简介
φ函数的值通式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1,p2……pn为x的所有质因数,x是不为0的整数。φ(1)=1(唯一和1互质的数(小于等于1)就是1本身)。(注意:每种质因数只一个。比如12=2*2*3那么φ(12)=12*(1-1/2)*(1-1/3)=4
若n是质数p的k次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了p的倍数外,其他数都跟n互质。
设n为正整数,以φ(n)表示不超过n且与n互
素的正整数的个数,称为n的欧拉函数值,这里函数
φ:N→N,n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。
特殊性质:当n为奇数时,φ(2n)=φ(n),证明与上述类似。
若n为质数则φ(n)=n-1。
编程实现
利用欧拉函数和它本身不同质因数的关系,用筛法计算出某个范围内所有数的欧拉函数值。
欧拉函数和它本身不同质因数的关系:欧拉函数ψ(N)=N{∏p|N}(1-1/p)亦即:ψ(N)=(P是数N的质因数)
如:
ψ(10)=10×(1-1/2)×(1-1/5)=4;
ψ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
ψ(49)=49×(1-1/7)==42。