Problem 47 - 異なる素因数
ガンガンいくよ。
連続する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
だいぶ集合に慣れてきた気がする。