« Project Euler 用関数 (Haskell) | トップページ | Project Euler : Problem 38 ~ Pandigital な連結積 »

2010年7月22日 (木)

Project Euler : Problem 37 ~ 左右から切り詰め可能な素数

 問題はこちらをご覧ください。
 また、自作の "ForEuler module" に関してはこちらをご覧ください。

 

 まずは brute force 版から……。

import ForEuler -- 左右どちらからも切り詰め可能か? -- ex : n = 3797 の時、xs は [(379,7),(37,97),(3,797)] となる。 isTruncatable :: Int -> Bool isTruncatable n = and [isPrime q && isPrime r | (q, r) <- xs] where xs = map (quotRem n) $ takeWhile (< n) $ iterate (* 10) 10 -- 左右どちらからも切り詰め可能な素数 (一桁の素数を除く) truncatablePrimes :: [Int] truncatablePrimes = take 11 [x | x <- dropWhile (< 10) primes, isTruncatable x] problem037 :: Int problem037 = sum truncatablePrimes main :: IO () main = print problem037
 工夫したのは、左から切り詰める場合の判定と右から切り詰める場合の判定をひとつの関数で行った所でしょうか?
 例えば、問題に出てくる 3797 という素数が左右から切り詰め可能であるためには、797, 97, 7, 379, 37, 3 の全てが素数である必要があります。
 isTruncatable 関数はコメントに書いてあるように、3797 が与えられると一度に [(379,7),(37,97),(3,797)] というリストを作って、全てが素数かどうかを調べます。

 さらに別の方法でも解いてみました。
 Scheme 版にも書いた方法で、素数の右に数字をつけて新しい素数を作っていくものです。(詳しくは Scheme 版の解説をご覧ください)

import ForEuler -- 整数 n の右に数字をつけて新しい素数を作る。 -- ex : makeNewPrimes 3 => [31, 37] makeNewPrimes :: Int -> [Int] makeNewPrimes n = filter isPrime [10 * n + x | x <- [1,3,7,9]] -- 左から切り詰められるか? -- ex : n = 3797 の時、xs は [7, 97, 797] となる。 isTruncatable :: Int -> Bool isTruncatable n = and [isPrime x | x <- xs] where xs = [rem n x | x <- takeWhile (< n) $ iterate (* 10) 10] -- 左右どちらからも切り詰め可能な素数 (一桁の素数を除く) truncatablePrimes :: [Int] truncatablePrimes = filter isTruncatable xs where xs = dropWhile (< 10) $ concat $ takeWhile (not . null) xss xss = iterate (concatMap makeNewPrimes) [2, 3, 5, 7] problem037 :: Int problem037 = sum truncatablePrimes main :: IO () main = print problem037
 こちらは調べる数がかなり少ないので、最適化してコンパイルした場合、0.02 秒ほどで答えが出ました。ひとつめの方法が同じ条件で 0.36 秒ほどかかっているので、アルゴリズムを変えただけでかなり高速化されたと言えます。

« Project Euler 用関数 (Haskell) | トップページ | Project Euler : Problem 38 ~ Pandigital な連結積 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 37 ~ 左右から切り詰め可能な素数:

« Project Euler 用関数 (Haskell) | トップページ | Project Euler : Problem 38 ~ Pandigital な連結積 »

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

最近のトラックバック

無料ブログはココログ