はすけるとぱいそん

Project Euler 35

Haskell, Project Euler

問題はこちら。
この問題はネットを少々徘徊した限りでは、僕のコードが一番速かったです。
ちょっとうれしい。えへへ。すごいね！おにいちゃん！！！
（とりあえずうｐ。コメント、メモはあとでまた書こ）

import Data.List
import Data.Char


f :: [Int] -> Integer
f xs = read (map intToDigit xs) :: Integer

a :: [Integer]
a = 2:5:(map f $ concat $ map (nub.permutations) $ concat [ comb [1,3,7,9] x | x <- [1..6] ])

g:: Integer -> Integer
g n = read (map (intToDigit) (tail ns ++ [head ns]))::Integer
	  where ns = map (digitToInt) (show n)

h' :: Integer -> Int -> Bool
h' n c 
	| (c == length (show n)) = True
	| isPrime n = h' (g n) (c+1)
	| otherwise = False

h :: Integer -> Bool
h n = h' n 0

main = print $ length $ filter h a



--重複組み合わせ。
comb :: [a] -> Int -> [[a]]
comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) n = map (x:) (comb (x:xs) (n-1)) ++ comb xs n


--素数の無限リスト。
primesList :: [Integer]
primesList = map fromIntegral primesList'
    where
      primesList' = [2, 3, 5] ++ f 5 7 (drop 2 primesList')
      f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
          where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]


--素数判定。
isPrime :: Integer -> Bool
isPrime n = (n > 1) && isPrime' primesList
    where
      isPrime' (x : xs)
          | x * x > n    = True
          | rem n x == 0 = False
          | otherwise    = isPrime' xs

ツイートする

Permalink | コメント(0) | トラックバック(0) | 15:29