分类： Level3

在数论中，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数量，表示为φ(n)。

根据唯一分解定理，n=P1^a1P2^a2P3^a3……Pn^an，这里P1<P2<P3……<Pn 均为质数，其中指数ai是正整数。则φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*…*(1-1/pn)。