Euler's Phi Function

Euler's Phi Function

這是一個公式。它可以算出所有比n小,又跟n互質的數有幾個。

首先要將n做質因數分解:

n = (p1^a1) * (p2^a2) * ... * (pk^ak)  where p1, ..., pk are primes

然後利用上面的值來計算Euler's Phi Function:

Φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

在計算的時候,可以以這個順序計算,避免溢位的問題:

n / p1 * (p1 - 1) / p2 * (p2 -1) / p3 * (p3 - 1) / ... / pk * (pk - 1)

由於p1、p2、…、pk都是n的質因數,故可以整除n。

使用Euler's Phi Function比一個一個數檢查還要有效率!相當有用。

UVa 10299 10179

Φ(p) = p - 1                      iff p is prime.
Φ(p^a) = p^a - p^(a-1)            iff p is prime.
Φ(n*m) = Φ(n) * Φ(m)              iff n and m are relatively prime.
Φ(n) = Φ(p1^a1) * ... * Φ(pk^ak)  iff n = (p1^a1) * ... * (pk^ak)
                                      where p1, ..., pk are prime.