« Turtle Graphics on Ruby/SDL ver.2.0 | トップページ | Project Euler --- Problem 2 »

2009年1月 9日 (金)

Project Euler --- Problem 5

Problem 5 は「 1 から 20 までの整数全てで割り切れる数字の中で最小の値を求める」というものでした。

これは、「 1 から 20 までの全ての整数の最小公倍数を求める」ということになります。

Scheme には最小公倍数を求める lcm という手続きがあるので、

 (apply lcm (cdr (iota (+ 20 1))))

とすれば、一発で答えが出ます。

二つの整数 a, b の最大公約数を GCM(a, b), 最小公倍数を LCM(a, b) とすると、

  LCM(a, b) = a * b / GCM(a, b)

となるので、最小公倍数を求める手続きのないプログラム言語でも、ユークリッドの互除法を使って二つの整数の最大公約数を見つける手続きを自分で作ってしまえば、あとは、 1 から 20 までの数の最小公倍数を順に探していけばいいはずです。

« Turtle Graphics on Ruby/SDL ver.2.0 | トップページ | Project Euler --- Problem 2 »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/43677592

この記事へのトラックバック一覧です: Project Euler --- Problem 5:

« Turtle Graphics on Ruby/SDL ver.2.0 | トップページ | Project Euler --- Problem 2 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ