Project Euler: Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

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

1 から 20 までの全ての数で割り切れる最小の数を求めよとのこと。

Gauche で書いてみた。これまでの問題よりもすんなりできた気がするが、ちょっと汚いか。

#!/usr/bin/env gosh

;; 素数かどうか判定する (遅い)
(define (prime? 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
              (loop (+ i 2) m))
            n)))]))

(define (main args)
  (define nmin 1)  ; 1 から
  (define nmax 20) ; 20 まで

;; 1 から 20 までの範囲の全ての素数の積を求める
  (define x (fold *
                  1   
                  (let loop [(n nmin)
                             (lis '())]
                    (if (<= n nmax)
                      (loop (+ n 1) (if (prime? n) (cons n lis) lis))
                      lis))))

;; 範囲内の素数の積 (=> x) の倍数を順に求めて割り切れるか判定する
  (let xtest [(ax x)
              (a 1)]
    (if (let loop [(n nmin)] ; 1 から 20 までの全ての数で割り切れるか判定する
          (if (<= n nmax)
            (if (= (remainder ax n) 0)
              (loop (+ n 1))
              #f)
            ax))
      (print ax)
      (xtest (* x (+ a 1)) (+ a 1)))) ; だめだったら a をインクリメントして再計算
  0)