Home

PureScript solution to Project Euler problem 7

2018-Apr-02 23:13
purescriptproject-euler

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.