P37 - Calculate Euler’s totient function ϕ ( m ) ϕ(m) (improved).

See problem P34 for the definition of Euler’s totient function.  If the list of the prime factors of a number mm is known in the form of problem P36 then the function ϕ(m)ϕ(m) can be efficiently calculated as follows: Let [[p1,m1],[p2,m2],[p3,m3],…][[p1​,m1​],[p2​,m2​],[p3​,m3​],…] be the list of prime factors (and their multiplicities) of a given number mm.  Then ϕ(m)ϕ(m) can be calculated with the following formula:

ϕ(m)=(p1−1)∗p1m1−1∗(p2−1)∗p2m2−1∗(p3−1)∗p3m3−1∗…ϕ(m)=(p1​−1)∗p1m1​−1​∗(p2​−1)∗p2m2​−1​∗(p3​−1)∗p3m3​−1​∗…

Note that abab stands for the bbth power of aa.