尤拉公式質數

歐拉函式，記作φ(N)，是指1到N中與N互質的數的個數。如果將N分解質因數，假設N=p1c1p2c2p3c3···pmcm，那麼歐拉函式φ(N)的計算公式為：φ(N)=N∗∏質數p|N(1−1p)。這個公式表明，歐拉函式是N與所有質因數的倒數的差值的乘積。