Project Eulerを(再び)はじめました Problem 5まで

久々。
というか、仕事やら趣味やらでRatedなコンテストに全然出られない。しばくぞ。

maspypy.com
この方の記事を読んで、久々にProject Eulerというものを思い出した。
そして、一時期ハマっていたこれを解いていこうと思ったのです。
早速日本語訳サイトを見て、ガンガン解いていきます。
なんか普通にやるのもなぁということで、Schemeで解くという縛りを自分に課しました。
この足枷が、いつか勉強の妨げになるだろうと思いながら・・・・

というわけで、数問解いたコードです。
DrRacketという環境でコーディング＆実行しています。

Problem 1

(define (ans limit)
  (define (sub now sum)
    (if (>= now limit) sum
        (if (= 0 (* (modulo now 3) (modulo now 5)))
            (sub (+ now 1) (+ sum now))
            (sub (+ now 1) sum))))
  (sub 1 0))

(display (ans 1000))

Problem 2

(define (fib-even-sum limit)
  (define (fib-sub first second sum)
    (if (> first limit) sum
        (fib-sub second (+ first second) (+ sum (if (= (modulo first 2) 0) first 0)))))
  (fib-sub 0 1 0))

(display (fib-even-sum 4000000))

ifの位置を工夫してかっこよくした。

Problem 3

(define (max-prime-factor n)
  (define (sub now max)
    (if (> (* now now) n) max
        (sub (+ now 1) (if (and (= (modulo n now) 0) (prime? now)) now max))))
  (sub 2 0))

(define (prime? n)
  (define (sub now)
    (cond ((= now n) #t)
          ((= 0 (modulo n now)) #f)
          (#t (sub (+ now 1)))))
  (sub 2))

(display (max-prime-factor 600851475143))

約数じゃなくて素因数。素数かどうか求める部分は特に高速化せず。

Problem 4

(define (hanten n)
  (define (sub num ans)
    (if (= num 0) ans
        (sub (quotient num 10) (+ (* ans 10) (modulo num 10)))))
  (sub n 0))

(define (solve n m maxhanten)
  (if (and (= n 1000) (= m 100)) maxhanten
      (solve (if (= m 999) (+ n 1) n) (if (= m 999) 100 (+ m 1)) (if (and (= (* n m) (hanten (* n m))) (> (* n m) maxhanten)) (* n m) maxhanten))))

(display (solve 100 100 0))

3桁*3桁で回文数があることを前提としたコードになってしまった。あと、solveのとこを場合分け減らすべく書いたらめちゃややこしくなってしまった。
(hanten n)の作り方は我ながらキレイ。

Problem 5

(define (multi-lcm n)
  (define (sub now lcmnum)
    (if (> now n) lcmnum
        (sub (+ now 1) (lcm now lcmnum))))
  (sub 1 1))

(multi-lcm 20)

もともとlcmとgcdという関数が入っているのね。

このあたりまでなら即答できるけど、どこかのタイミングで数時間〜数日かかるような問題に当たるんだろうな・・・
怖いけど、楽しみです。
一旦今日はここまで！