« Project Euler : Problem 33 | トップページ | Project Euler : Problem 34 »

2010年6月22日 (火)

Project Euler : Problem 35 ~ 循環素数

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

 

 基本的な解法は以前 Scheme や Ruby で解いたときと同じです。
 要素に「0, 2, 4, 5, 6, 8」を含む数は、最初が素数でも循環しているうちに必ず合成数(偶数または 5 の倍数)になってしまうので、即座に候補から除外し、それ以外の素数は、地道に循環させて素数になるかを調べています。

import Data.List (tails) -- 素数列 primes :: Integral a => [a] primes = map fromIntegral ([2, 3] ++ primes' :: [Int]) where primes' = 5 : sieve 1 sieve n = filter (`isPrime` primes') ns ++ sieve (n + 1000) where ns = [6 * x + y | x <- [n .. n + 999], y <- [1, 5]] isPrime m (x : xs) | x * x > m = True | rem m x == 0 = False | otherwise = isPrime m xs -- 素数判定 isPrime :: Integral a => a -> Bool isPrime n = (n > 1) && iter primes where iter (x : xs) | x * x > n = True | rem n x == 0 = False | otherwise = iter xs -- 整数 (十進法) -> リスト dexToList :: Integral a => a -> [a] dexToList n = iter n [] where iter n prd | n < 10 = n : prd | otherwise = iter (div n 10) (rem n 10 : prd) -- リスト -> 整数 (十進法) listToDex :: Integral a => [a] -> a listToDex ns = foldl calc 0 ns where calc x y = x * 10 + y -- 与えられた素数は循環素数か? isCircularPrime :: Int -> Bool isCircularPrime n = noEvenAnd5 xs && and [isPrime $ listToDex ys | ys <- yss] where noEvenAnd5 ys = and [y /= 5 && odd y | y <- ys] xs = dexToList n yss = tail $ take size $ map (take size) $ tails $ cycle xs where size = length xs -- 1000000 以下の循環素数 circularPrimes :: [Int] circularPrimes = as ++ filter isCircularPrime bs where (as, bs) = span (< 10) $ takeWhile (< 1000000) primes problem035 :: Int problem035 = length circularPrimes main :: IO () main = print problem035

 もう一つの方法として、重複順列を使って「1,3,7,9」しか含まない数を予め作っておいて、その数が循環素数になるかを調べてみました。

import Data.List -- 素数判定 -- isPrime :: Integral a => a -> Bool isPrime n = (n > 1) && iter primes' where iter (x : xs) | x * x > n = True | rem n x == 0 = False | otherwise = iter xs -- 擬似素数 primes' :: Integral a => [a] primes' = 2 : 3 : [x + y | x <- [6, 12 ..], y <- [-1, 1]] -- 整数をリストに変換 dexToList :: Integral a => a -> [a] dexToList n = iter n [] where iter n prd | n < 10 = n : prd | otherwise = iter (div n 10) (rem n 10 : prd) -- リストを整数に変換 listToDex :: Integral a => [a] -> a listToDex ns = foldl calc 0 ns where calc x y = x * 10 + y -- 重複順列 ( 辞書順 ) -- ex : repPermutation [1..3] 2 -- => [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]] repPermutation :: [a] -> Int -> [[a]] repPermutation ns n = perm n [[]] where size = length ns - 1 perm 0 xs = xs perm c xs = perm (c - 1) $ concatMap f xs f xs = [xs ++ [ns !! i] | i <- [0 .. size]] -- 与えられたリストを整数に変換したものは循環素数か? isCircularPrime :: [Int] -> Bool isCircularPrime ns = and [isPrime $ listToDex xs | xs <- xss] where size = length ns xss = take size $ map (take size) $ tails $ cycle ns -- 1000000 以下の循環素数 circularPrimes :: [Int] circularPrimes = [2, 3, 5, 7] ++ [listToDex xs | xs <- xss, isCircularPrime xs] where xss = concatMap (repPermutation [1, 3, 7, 9]) [2 .. 6] problem035 :: Int problem035 = length circularPrimes main :: IO () main = print problem035
 こちらの方がかなり速く答えが出せました。

« Project Euler : Problem 33 | トップページ | Project Euler : Problem 34 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 35 ~ 循環素数:

« Project Euler : Problem 33 | トップページ | Project Euler : Problem 34 »

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

最近のトラックバック

無料ブログはココログ