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 ==  = factors25 (m2+1,m5) (div n 2)
| mod n 5 ==  = factors25 (m2,m5+1) (div n 5)
| otherwise = (m2,m5)
check n = powMod 10 (10^(max num2 num5)) n == 1
where (num2,num5) = factors25 (,)$ n - 1
main = print.(+3).sum.filter(not.check).takeWhile(<upper)$primes
upper = 10^5