Home

PureScript solution to Project Euler problem 3

2017-Dec-01 00:18
purescriptproject-euler

Problem details at Project Euler problem 3 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
module Euler003Test (euler3suite) where
 
import Prelude
 
import Data.Decimal (fromInt, fromString)
import Data.Maybe (Maybe(..))
import Euler003 (euler3)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler3suite :: forall e. TestSuite e
euler3suite =
  suite "Euler 3" do
    test "Warmup" do
      case fromString "13195" of
        Just d ->  Assert.equal (fromInt 29) (euler3 d)
        Nothing -> Assert.assert "fromString failed" false
    test "Real" do
      case fromString "600851475143" of
        Just d ->  Assert.equal (fromInt 6857) (euler3 d)
        Nothing -> Assert.assert "fromString failed" false

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
module Euler003 (euler3) where
 
import Prelude
 
import Data.Decimal (Decimal, floor, fromInt, modulo, sqrt)
import Data.Foldable (maximum)
import Data.List.Lazy (drop, iterate, takeWhile)
import Data.Maybe (fromMaybe)
 
minFactor :: Decimal -> Decimal
minFactor n = go (fromInt 2)
  where ubound = sqrt n # floor
        go k | k > ubound = n
             | n `modulo` k == fromInt 0 = k
             | otherwise = go (k + fromInt 1)
 
euler3 :: Decimal -> Decimal
euler3 n =
  iterate (\{k, f} -> let mf = minFactor k in {k: k / mf, f: mf})
          {k: n, f: fromInt 1}
  # drop 1
  # takeWhile (\{k, f} -> f > fromInt 1)
  # map (\{k, f} -> f)
  # maximum
  # fromMaybe (fromInt 1)

Comments

Mostly relying on the underlying purescript-decimals.