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)