Problem 72 - 既約分数の数

かなり重かった。

1/dとして、d <= 100万まで既約分数の個数を答える。

オイラーの関数で簡単に。と思ったけど、100万までの全ての数について素因数分解したのと変わらない訳。

100万 * √100万 = 10億。

多く見積もって10億回。少なく見積もっても1億回くらい。時間計り忘れたけど、かなりかかる。

もっとうまいやり方がありそう。

(define (phi n)
  (letrec ((iter (lambda (t p)
                   (cond ((= t 1) n)
                         ((> p (sqrt n)) (* n (- 1 (/ 1 t))))
                         (else
                           (if (zero? (modulo t p))
                               (* (- 1 (/ 1 p))
                                  (iter
                                    (do ((tt t (quotient tt p)))
                                      ((not (zero? (modulo tt p))) tt))
                                    (+ p (modulo p 2) 1)))
                               (iter t (+ p (modulo p 2) 1))))))))
    (iter n 2)))

(define (problem72 n)
  (fold (lambda (n acc)
          (+ (phi n) acc))
        0
        (iota (- n 1) 2)))

(problem72 10) ; 31
(problem72 100) ; 3043
(problem72 1000) ; 304191
(problem72 10000) ; 30397485
(problem72 100000) ; 3039650753
(problem72 1000000) ; 303963552391