Chapter 03

Problem 3: Largest prime factor

aoi.iter
aoi.iter
2022.06.23に更新
このチャプターの目次

2022/06/21

https://projecteuler.net/problem=3

問題

13195 の素因数は 5, 7, 13, 29 である.

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

考察

対象の数値aが数列a(2, 3, 4, ...)のa_n項で割り切れる場合に割る処理を続ける
a <= a_nとなったときのaが最大の素因数になる

解答

; https://projecteuler.net/problem=3
(define (divisible? n x)
  (zero? (mod n x)))

(define (solve target)
  (letrec ((solve-rec (lambda (n a)
                        (cond ((<= n a) n)
                              ((divisible? n a) (solve-rec (/ n a) (+ a 1)))
                              (else (solve-rec n (+ a 1)))))))
    (solve-rec target 2)))

(solve 13195)
; => 29
(solve 600851475143)
; => 6857

感想

N/A

参考資料

N/A