« Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム | トップページ | Haskell で fibonacci »

2009年11月23日 (月)

Project Euler - Problem 3 : 素因数分解

問題はこちらをご覧ください。


この問題は要するに素因数分解の問題です。自作の手続き "factorize" を使うのなら、

(define problem-003-1 (lambda (n) (caar (last-pair (factorize n))))) > (time (problem-003-1 600851475143)) (time (problem-003-1 600851475143)) no collections 1 ms elapsed cpu time 1 ms elapsed real time 24272 bytes allocated

これだけで終わってしまいます。

でも、わざわざ素因数分解の手続きを作らなくても、2 で繰り返し割った後、奇数の小さい方から順に割り続けるだけでも答えは出ます。

(define problem-003-2 (lambda (n) (define divide (lambda (n i) (cond ([= n 1] i) ([zero? (remainder n i)] (divide (/ n i) i)) (else n)))) (let loop ([n (divide n 2)] [i 3]) (if [> (* i i) n] n (loop (divide n i) (+ i 2)))))) > (time (problem-003-2 600851475143)) (time (problem-003-2 600851475143)) no collections 1 ms elapsed cpu time 1 ms elapsed real time 144 bytes allocated

« Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム | トップページ | Haskell で fibonacci »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler - Problem 3 : 素因数分解:

« Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム | トップページ | Haskell で fibonacci »

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            
フォト

最近のトラックバック

無料ブログはココログ