August 19, 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. Then phi(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 a ** b stands for the b'th power of a.
lisp
(load "p36.lisp")
(defun phi2 (n)
(phi-list (prime-factors-mult n))
)
(defun phi-list (lista)
(if (null lista)
1
(* (1- (caar lista)) (expt (caar lista) (1- (cadar lista)))
(phi-list (cdr lista))
)
)
)
Be first to comment