Project Euler第72题

pro72.lisp

;;; 换个思路？
;;; 先算出一百万以下的所有素数
;;; 基于这个素数表，对每一个数字d都进行快速的因数分解
;;; 得到数字d的质因数后，用筛法计算出互质的数字的个数
(defun generate-prime-numbers (limit)
  "计算出所有不大于LIMIT的素数。"
  (let ((bitmap (make-array limit :initial-element 1))
        (result '()))
    (dotimes (i limit (nreverse result))
      (let ((ele (aref bitmap i)))
        ;; 如果ele已经是0了，便不是素数，也就不用做进一步判断了。
        (when (= ele 1)
          (let ((n (1+ i)))
            ;; 跳过1，因为1是素数并且是所有数字的因数
            (when (> n 1)
              (push n result)
              ;; 把属于当前数字的倍数对应的下标的元素赋值为0
              (do* ((times 2 (1+ times))
                    (j (1- (* times n)) (1- (* times n))))
                   ((> j (1- limit)))
                (setf (aref bitmap j) 0)))))))))

(defvar *prime-numbers* (generate-prime-numbers 1000000)
  "不大于一百万的素数。")

(defun factoring (n)
  "返回N的质因数。"
  (labels ((aux (n ps result)
             (let ((f (first ps)))
               (cond ((= n 1)
                      result)
                     ((zerop (mod n f))
                      (aux (/ n f) ps (if (equal f (car result)) result (cons f result))))
                     (t
                      (aux n (rest ps) result))))))
    (aux n *prime-numbers* '())))

;;; 用因数分解加筛法来寻找互质的数字
(defun count-coprime-numbers (d)
  "数出小于D并且与D互质的正整数。"
  (let ((bitmap (make-array d :initial-element 1))
        (factors (factoring d)))
    (dolist (f factors)
      (do ((i (1- f) (+ i f)))
          ((> i (1- d)))
        (setf (aref bitmap i) 0)))
    (count-if #'(lambda (ele)
                  (= ele 1))
              bitmap)))

(defun count-coprime-numbers-by-formula (d)
  "用欧拉函数计算与D互质的数的个数。"
  (* d
     (reduce #'(lambda (acc n)
                 (* acc (- 1 (/ 1 n))))
             (factoring d)
             :initial-value 1)))

(defun count-total-reduced-proper-fractions (d)
  "计算所有不大于D的正整数的reduced proper fraction的数量。"
  (let ((count 0))
    (dotimes (i d (1- count))
      (let ((nd (1+ i)))
        (when (zerop (mod nd 1000))
          (format t "已处理~D个数字~%" nd))
        (incf count (count-coprime-numbers-by-formula nd))))))