Project Euler 33,35

Haskell

Problem 33

http://projecteuler.net/index.php?section=problems&id=33


11の倍数はダメ。



is_cancellable (x, y) = f x y || f y x where

        f x y = (div y 10) == (mod x 10) && x * (mod y 10) == y * (div x 10)
a :: [(Int,Int)]

a = filter is_cancellable [ (x, y) |

                x <- [10..98], y <- [11..99], x < y && (mod y 11) /= 0 ]

[n, d] = map product [ fst c, snd c ] where c = unzip a

main = print(div d (gcd n d))

Problem 35

http://projecteuler.net/index.php?section=problems&id=35


回転させてすべて素数か調べるだけ。



import Data.Array
sieve a p | a!p == True = sieve (a // [ (m, False) | m <- b, a!m ]) (p + 1)

          | p * p > n = a

          | otherwise  = sieve a (p + 1)

                where b = if p == 2 then [p*2,p*3..n] else [p*3,p*5..n]
digits 0 = []

digits n = (digits (div n 10)) ++ [mod n 10]

numerize a = foldl (\x y -> x * 10 + y) 0 a
rotate n = numerize ((tail a) ++ [head a]) where a = (digits n)

rot_list n = n:(takeWhile (\m -> m /= n) (map rotate (rot_list n)))
is_zero_less n = all (\d -> d /= 0) (digits n)

is_valid n = is_zero_less n && all (\n -> a!n) (rot_list n)
circular_prime [] = []

circular_prime (n:ns) | is_valid n = n:(circular_prime ns)

                      | otherwise  = circular_prime ns
n = 10^6

a = sieve (array (2, n) [ (k, True) | k <- [2..n] ]) 2

main = print(length (circular_prime (filter (\n -> a!n) [2..n])))

しかし、これはエラトステネスのふるいが遅い。
2桁以上なら各桁は1,3,7,9でなければならないので、これで数を生成すれば個数がぐっと減るので、直接素数判定してもよい。



is_prime n = all (\p -> mod n p /= 0)

        (takeWhile (\p -> p * p <= n) (2:[3,5..]))
digits 0 = []

digits n = (digits (div n 10)) ++ [mod n 10]

numerize a = foldl (\x y -> x * 10 + y) 0 a
rotate n = numerize ((tail a) ++ [head a]) where a = (digits n)

rot_list n = n:(takeWhile (\m -> m /= n) (map rotate (rot_list n)))
is_zero_less n = all (\d -> d /= 0) (digits n)

is_valid n = is_zero_less n && all is_prime (rot_list n)
circular_prime [] = []

circular_prime (n:ns) | is_valid n = n:(circular_prime ns)

                      | otherwise  = circular_prime ns
numbers 0 = [0]

numbers n = concat (map (\m -> map (\k -> k * 10 + m) (numbers (n - 1)))

                                                                [1,3,7,9])
n = 6

b = [2..9] ++ (concat (map numbers [2..n]))

main = print(length (circular_prime (filter is_prime b)))