## Project Euler Problem 381

Project Euler Problem 381 is easy problem. Using Wilson theorem

Haskell source code using monad par

import Data.List import Data.Numbers.Primes import Control.Monad.Par import GHC.Conc.Sync --use wilson theorem ( p - 1 ) ! = -1 mod p prime = drop 2 . takeWhile ( < 10 ^ 8 ) $ primes extendedGcd :: Int -> Int -> ( Int , Int ) extendedGcd a b | b == 0 = ( 1 , 0 ) | otherwise = ( t , s - q * t ) where ( q , r ) = quotRem a b ( s , t ) = extendedGcd b r modInv :: Int -> Int -> Int modInv a b | gcd a b /= 1 = error " gcd is not 1 " | otherwise = d where d = until ( > 0 ) ( + b ) . fst.extendedGcd a $ b computeFinal :: Int -> Int computeFinal p = computeS ( p - 1 ) 0 1 where computeS inv ret cnt | cnt >= 5 = mod ( ret + inv ) p | otherwise = computeS ( mod ( inv * inv' ) p ) ( mod ( ret + inv ) p ) ( cnt + 1 ) where inv' = modInv ( p - cnt ) p chunk :: [ Int ] -> Int -> [ [ Int ] ] chunk xs n = ret where tot = numCapabilities brk = div n tot ret = unfoldr fun ( xs , 1 ) where fun ( xs' , cnt ) | null xs' = Nothing | cnt >= tot = Just ( xs' , ( [] , cnt ) ) | otherwise = Just ( a , ( b , cnt + 1 ) ) where ( a , b ) = splitAt brk xs' ans = ret' where ret = runPar $ parMap ( map computeFinal ) ( chunk prime len ) len = length prime ret' = sum . map sum $ ret main = do print ans

Compile it “ghc-7.4.1 -O2 -rtsopts -threaded -fforce-recomp Euler_381.hs” and run it with as many cores you have. My run time is

[mukesh@user Euler]$ time ./Euler_381 +RTS -A16M -H2G -N8 -RTS

139602943319822

real 0m28.473s

user 0m58.204s

sys 0m21.713s

Advertisements

No comments yet.

Advertisements

## Leave a Reply