Problem 47 - 異なる素因数

ガンガンいくよ。


Problem 47 - PukiWiki

連続する3つの数がそれぞれ3つの異なる素因数を持つものは、こんなんで、

  • 644 = 2^2 × 7 × 23
  • 645 = 3 × 5 × 43
  • 646 = 2 × 17 × 19

連続する4つの数がそれぞれ4つの異なる素因数を持つものを答える。


2^2と2は異なる素因数らしい。しかも2^2は一個と数えるみたい。


異なる素因数の定義がちと面倒だ。


644なら素因数分解してみて、2が2個、7が1個、23が1個として、素因数の長さとキャッシュの積集合で比較していくことにする。

(define (factor n)
  (letrec ((iter
             (lambda (i m)
               (cond ((= m 1) '())
                     ((zero? (modulo m i)) (cons i (iter i (quotient m i))))
                     ((> i (sqrt m)) (list m))
                     (else
                       (iter (+ i
                                (if (= i 2) 1 2))
                             m))))))
    (iter 2 n)))

(define (collect l)
  (let ((c (list)))
    (for-each
      (lambda (x)
        (let ((f (assoc x c)))
          (if f
              (set-cdr! f (+ (cdr f) 1))
              (set! c (cons (cons x 1) c)))))
      l)
    c))

(define (problem47 n)
  (letrec ((iter
             (lambda (i acc facts)
               (if (= (length acc) n)
                   acc
                   (let ((fac (collect (factor i))))
                     (if (and (= (length fac) n)
                              (null? (lset-intersection equal? fac facts)))
                         (iter (+ i 1) (cons i acc) (append fac facts))
                         (iter (+ i 1) '() '())))))))
    (last (iter 1 '() '()))))

(time (problem47 4))
; cpu time: 1912 real time: 1912 gc time: 53
; 134043

だいぶ集合に慣れてきた気がする。