这是欧拉φ函数的公式：

　　φ(n)：小于n的数里,与n互质的数的个数.

　　公式是这样的：

　　先把n进行质因数分n=p1^k1*p2^k2*...*pr^kr

　　则：φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pr)

　　比如：n=60=2^2*3*5

　　那么：φ(n)=60*(1-1/2)(1-1/3)(1-1/5)=16

　　再比如：n=36=2^3*3^2

　　那么：φ(n)=36*(1-1/2)(1-1/3)=12

　　证明是这样的.

　　先证明一个引理：如果m、n互质,则：φ(mn)=φ(m)φ(n)

　　然后质因数分解中,p1^k1、p2^k2、...、pr^kr都是互质的,并且对于质数p：

　　φ(p^k)=p^k-p^(k-1)=p^k(1-1/p)

　　所以乘起来后：

　　φ(n)=φ(p1^k1)φ(p2^k2)...φ(pr^kr)

　　=p1^k1(1-1/p1)*p2^k2(1-1/p2)*...*pr^kr(1-1/pr)

　　=n(1-1/p1)(1-1/p2)...(1-1/pr)

　　蟹蟹你！