icyrock.com
HomePureScript solution to Project Euler problem 7
2018-Apr-02 23:13
Problem details at Project Euler problem 7 page.
Test
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | module Euler007Test (euler7suite) where import Prelude import Data . Maybe ( Maybe ( .. )) import Euler007 (euler7) import Test . Unit (TestSuite, suite, test) import Test . Unit . Assert as Assert euler7suite :: forall e . TestSuite e euler7suite = suite "Euler 7" do test "Warmup" do Assert . equal ( Just 13 ) (euler7 6 ) test "Real" do Assert . equal ( Just 104743 ) (euler7 10001 ) |
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | module Euler007 where import Prelude import Control . Monad . Eff ( Eff , forE) import Control . Monad . ST (ST, pureST) import Data . Array ( drop , filter , ( !! ), ( .. )) import Data . Array . ST (STArray, pokeSTArray, withArray) import Data . Int ( floor , toNumber) import Data . Maybe ( Maybe ) import Math ( log , sqrt ) floorF :: (Number - > Number) - > Int - > Int floorF f = floor <<< f <<< toNumber crosser :: forall h . Int - > STArray h Int - > Eff (st :: ST h) Unit crosser n a = let sn = 1 + floorF sqrt n in forE 2 sn \ i - > do let u = 1 + n / i forE i u \ j - > do void $ pokeSTArray a (j * i) 0 genTable :: Int - > Array Int genTable n = pureST (withArray (crosser n) ( 0 .. n)) genPrimes :: Int - > Array Int genPrimes n = filter ( _ /= 0 ) $ drop 2 $ genTable n euler7 :: Int - > Maybe Int euler7 n = let lnf x = x * ( log x + log ( log x)) lnn = floorF lnf n in genPrimes lnn !! (n - 1 ) |
Comments
Classic Sieve of Eratosthenes.
Upper bound estimation based on Approximations for the nth prime number.