problem 3 - mtsuyuguの日記

600851475143 の最大の素因数を求める問題。

素数ストリームで地道にループ。

(use util.stream)

(define divisible? (lambda (n d) (= (modulo n d) 0)))
(define square (lambda (x) (* x x)))

(define (integers-starting-from n)
    (stream-cons n (integers-starting-from (+ n 1))))

(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) #t)
          ((divisible? n (stream-car ps)) #f)
          (else (iter (stream-cdr ps)))))
  (iter primes))

(define primes
  (stream-cons
    2
    (stream-filter prime? (integers-starting-from 3))))

(define (p4)
  (let* ((target 600851475143)
         (limit (sqrt target)))
    (let loop ((p primes)
               (answer 2))
      (let1 prime (stream-car p)
            (if (> prime limit)
              answer
              (loop (stream-cdr p) (if (= (modulo target prime) 0)
                                     prime answer)))))))

(display (p4))

もっと効率の良い方法はあるのでしょうか。

目的を振り返る

d:id:mtsuyugu:20080610:1213104576 で SICP で stream を勉強する目的として

遅延評価とストリームが scheme でどう実装されるのかが分かっていないので、そこを理解する。

素数の無限ストリームを作って、project euler の問題を解くのに使ってみたい。

と書いたけど、これは達成できた。素数の無限ストリームに関しては自分で作ってないので全てが自力達成ではないけれど。