Problem 3

もう一問がんばる。

Problem 3 - PukiWiki

13195 の素因数は 5、7、13、29 である。

600851475143 の素因数のうち最大のものを求めよ。

素因数分解か!!


何も考えずに。ただひたすら。

(define (problem3 n)
  (define (iter m x l)
    (cond ((zero? (modulo m x)) (iter (/ m x) x (cons x l)))
          ((or (= m 1) (> x (sqrt n))) l)
          (else
            (iter m (+ x 1) l))))
  (iter n 2 '()))

(problem3 6)
(problem3 600851475143)

(problem3 13195) ; (29 13 7 5)
(problem3 600851475143) ; (6857 1471 839 71)

; 検算
(* 6857 1471 839 71) ; 600851475143

6857。

素数リストをあらかじめ用意しておくと早い。


これくらい易しい問題ならいいんだけど・・・。