Euler Project 69

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n  10.

Find the value of n  1,000,000 for which n/φ(n) is a maximum.

My Solution

(defun  primep (n)

        (cond ((minusp n) 'nil)

                  ((= 2 n) t)

                  ((evenp n) 'nil)

                  ((= 1 n) 'nil)

                  (t (let ((limit (floor (sqrt n))))

                      (do ((i 3 (incf i 2)))

                            ((> i limit) t)

                            (if (= 0 (mod n i)) (return-from primep 'nil)))))))

(defun totient(n)

  (let ((primelist (loop for i from 1 to (floor (sqrt n))

                                when (and (zerop (rem n i))

                                                (primep i))

                                collect i

                                when (and (integerp (/ n i))

                                                (primep (/ n i))

                                                (null (eq (/ n i) i)))

                                collect (/ n i))))

    (* n (apply #'*

                    (mapcar #'(lambda(x)(/ (- x 1) x))

                                primelist)))))

(defun Euler69(n)

  (let ((maxn 0)

         (currentnum 0)

         (maxnum 0)) 

    (loop for i from 5 to n

            do(progn (setq currentnum (/ i (totient i)))

                          (if (> currentnum maxnum)

                              (progn (setq maxnum currentnum)

                                        (setq maxn i)))))

    maxn))