P37: Calculate Euler's totient function phi

L-99の問題文では各素数の演算に対する和になっているけど、どうも積っぽい。

参照：http://www.geocities.com/hmaxf_urlcr/euler.htm [音が出るので注意]

;; P37
(defun fold1 (func n lis)
  (if (null lis) n
      (fold1 func (funcall func n (car lis)) (cdr lis))))

(defun totient-phi-v2 (m)
  (fold1 (lambda (prod l)
	   (let ((p (first l))
		 (m (second l)))
	     (* prod (* (1- p) (expt p (1- m)))))) 1 (prime-factor-mult m)))

(totient-phi 65535)
;; => 32768
(totient-phi-v2 65535)
;; => 32768