E(x)表示比x小的且與x互質(zhì)的正整數(shù)的個(gè)數(shù)。
*若p是素?cái)?shù)，E(p)=p-1。
*E(p^k)=p^k-p^(k-1)=(p-1)*P^(k-1)
證：令n=p^k,小于n的正整數(shù)數(shù)共有n-1即(p^k-1)個(gè),其中與p不質(zhì)的數(shù)共[p^(k-1)-1]個(gè)(分別為1*p,2*p,3*p...p(p^(k-1)-1))。
所以E(p^k)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1).得證。
*若ab互質(zhì)，則E(a*b)=E(a)*E(b)，歐拉函數(shù)是積性函數(shù).
*對(duì)任意數(shù)n都可以唯一分解成n=p1^a1*p2^a2*p3^a3*...*pn^an(pi為素?cái)?shù)).
則E(n)=E(p1^a1)*E(p2^a2)*E(p3^a3)*...*E(pn^an)     
      =(p1-1)*p1^(a1-1)*(p2-1)*p2^(a2-1)*...*(pn-1)*pn^(an-1)
      =(p1^a1*p2^a2*p3^a3*...*pn^an)*[(p1-1)*(p2-1)*(p3-1)*...*(pn-1)]/(p1*p2*p3*...*pn)
      =n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
* E(p^k)    =(p-1)*p^(k-1)=(p-1)*p^(k-2)*p
  E(p^(k-1))=(p-1)*p^(k-2)
->當(dāng)k>1時(shí)，E(p^k)=E(p*p^(k-1))=E(p^(k-1))*p.
  (當(dāng)k=1時(shí)，E(p)=p-1.)
由上式: 設(shè)P是素?cái)?shù)，
  若p是x的約數(shù)，則E(x*p)=E(x)*p.
  若p不是x的約數(shù)，則E(x*p)=E(x)*E(p)=E(x)*(p-1). 
*快速求歐拉函數(shù)方法：
 首先來(lái)回顧一下線性篩選素?cái)?shù)方法：
code
然后求歐拉函數(shù)：
Phi1


由以上思想，可以在篩選素?cái)?shù)的過(guò)程中求出歐拉函數(shù)：


Phi