Problem 133

http://projecteuler.net/index.php?section=problems&id=133
これも同様。
オイラーの定理（だっけ？）と前を利用。

import Number hiding(powMod)
powMod a n m | n < 3 = a^n `mod` m
             | otherwise = let (q,r) = divMod n 2
                               aq = powMod a q m
                           in aq*aq*a^r `mod` m

factors25 (m2,m5) n | mod n 2 == 0 = factors25 (m2+1,m5) (div n 2)
                    | mod n 5 == 0 = factors25 (m2,m5+1) (div n 5)
                    | otherwise = (m2,m5)

check n = powMod 10 (10^(max num2 num5)) n == 1
    where (num2,num5) = factors25 (0,0)$ n - 1

main = print.(+3).sum.filter(not.check).takeWhile(<upper)$primes
upper = 10^5