Project Euler: Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

http://projecteuler.net/index.php?section=problems&id=3

バカでかい合成数 (600851475143) を分解して得られる最大の素因数を求めよとのこと。

とりあえず Scheme でなんとか書けたが…。後から考えるとバカみたいに無駄が多かったようだ。とりあえず、恥晒しに載っけてみる。

#!/usr/bin/env gosh

;; 最大公約数を求める (実は R5RS にも同じ関数が含まれてたみたい)
(define (gcd a b)
  (if (< a b)
    (gcd b a) ; a より b が大きかったら入れ替えて再呼び出し
    (let loop ((a a)
               (b b))
      (let ((r (remainder a b))) ; ユークリッドの互除法
        (if (= r 0)
          b
          (loop b r))))))

(define (prime-deterministic? n) ; バカ正直に素数かどうか判定する (決定的)
  (case n
    [(1) #f]
    [(2) n]
    [else
      (if (even? n)
        #f
        (let loop ((i 3) ; minumum odd prime
                   (m (floor->exact (sqrt n))))
          (if (<= i m)
            (if (= (remainder n i) 0)
              #f ; i で割り切れたら #f
              (loop (+ i 2) m))
            n)))])) ; 全ての i で割り切れなかったとき

(use srfi-27)
(define (prime-fermat? n) ; フェルマー法で素数を判定する (確率的)
  (define (fermat? n a)
    (= (remainder (expt a (- n 1)) n) 1)) ; フェルマーの小定理
  (case n
    [(1) #f]
    [(2) #t]
    [else
      (let test_a ((a (random-integer n)))
        (if (and (< 1 a n)
                 (= (gcd n a) 1)) ; n と互いに素な乱数 a を求める
          (fermat? n a)
          (test_a (random-integer n))))])) ; 乱数が不適切だったら再呼び出し

(define prime? prime-fermat?)

(define (main args)
;; 約数を集めるためのリスト
  (define factors '())

;; 約数に分解して factors に加える
  (let find-factor ((i 2)
                    (n 600851475143)
                    (lis factors))
    (if (<= i n)
      [begin
        (if (= (remainder n i) 0)
          (find-factor (+ i 1)
;                      (quotient n i)
;; n を i で完全に割り切っておくことで、素数以外の約数をスキップする
                       (let loop ((n n)) ; n を i で完全に割り切る
                         (if (= (remainder n i) 0)
                           (loop (quotient n i))
                           n))
                       (cons i lis))
          (find-factor (+ i 1)
                       n
                       lis))]
      (set! factors lis)))
; (print factors)

;; 約数のリストから最大の素数を求める
;; (実際には、find-factor の部分で既に素数のみが選ばれている
  (let find-prime ((lis factors))
    (if (and (pair? lis)
             (prime? (car lis)))
      (print (car lis))
      (find-prime (cdr lis))))
  0)