letrecで繰り返す

Project EulerのProblem3をやった。
問題は素因数分解で、最大の素数を求めるもの。
素数を求めて割り切れるか確かめていけばいいだけだ。実に簡単…、じゃなかった。
分解する数が600851475143と超でかい。intじゃ収まらない。と思ったら、Lisp系の言語は多倍長演算してくれるようなので問題なかった。

素因数分解の方法としては、小さい素数から順次割り切れるかどうか確かめていく。割り切れれば、その商を割る数にして処理を継続する。素数が商以上になれば終了。てな感じである。

letrecを覚えたので使ってみた。

; 素数か？
(define prime-number?
  (lambda (m)
    (if (< m 2)
	#f
	(letrec ((find-prime
		  (lambda (i n)
		    (if (< i 2)
			#t
			(if (= 0 (remainder n i))
			    #f
			    (find-prime (- i 1) n))))))
	  (find-prime (- m 1) m)))))

; x以下の素数を求める
(define prime-below-x
  (lambda (x)
    (letrec ((rec-func
	      (lambda (i)
		(if (< i 2)
		    2
		    (if (prime-number? i)
			i
			(rec-func (- i 1)))))))
      (rec-func x))))

; 問題を解く、素因数分解
(define problem3
  (lambda (x)
    (letrec ((rec-func
	      (lambda (i x)
		(let ((p (prime-below-x i)))
		  (if (<= x p)
		      p
		      (if (= 0 (remainder x p))
			  (rec-func (+ i 1) (/ x p))
			  (rec-func (+ i 1) x)))))))
      (rec-func 2 x))))

答えは6857
(prime-number? 6857)
は#tを返したので、確かに最大の素数のようだ。