# Problem 37

(Intermediate 🌟🌟) Calculate Euler's totient function `φ(m)`

(improved).

See Problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number `m`

is known in the form of Problem 36 then the function `φ(m)`

can be efficiently calculated as follows: Let `[(p₁, m₁), (p₂, m₂), (p₃, m₃), ...]`

be the list of prime factors (and their multiplicities) of a given number `m`

. Then `φ(m)`

can be calculated with the following formula:

$$ φ(m) = ∏_{i=1}^{n} (p_i - 1) * p_i^{(m_i - 1)} $$

```
/-- the list of prime factors and their multiplicities of `n` -/
abbrev PrimeFactor := List (Nat × Nat)
def φ (_n : Nat) (factors : PrimeFactor) : Nat :=
sorry
-- The following codes are for test and you should not edit these.
#guard φ 10 [(2, 1), (5, 1)] = 4
#guard φ 20 [(2, 2), (5, 1)] = 8
#guard φ 39 [(3, 1), (13, 1)] = 24
```