August 23, 2024
P37 - Calculate Euler's totient function phi(m) (improved).
See problem P34 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 P36 then the function phi(m>) can be efficiently calculated as follows: Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m. Thenphi(m)can be calculated with the following formula:
phi(m) = (p1-1)*p1(m1-1) * (p2-1)*p2(m2-1) * (p3-1)*p3(m3-1) * ...
Note that ab stands for the bth power of a.
erlang
-module(p37).
-export([phi/1]).
phi(M) ->
Ls = p36:primeFactorMultiplicity(M),
maps:fold(fun(Elem,Mul, Ans) -> Ans * ((Elem -1) * math:pow(Elem, Mul -1)) end, 1.0, Ls).
Be first to comment