2023-07-13 16:34
Problem details at Project Euler problem 69 page.
module Euler069Test (euler69suite) where
import Prelude
import Data.Maybe (Maybe(..))
import Effect.Aff (Milliseconds(..), delay)
import Euler069 (euler69)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
euler69suite :: TestSuite
euler69suite =
suite "Euler 69" do
test "Warmup" do
delay (Milliseconds 0.0)
Assert.equal (Just 6) (euler69 10)
test "Real" do
delay (Milliseconds 0.0)
Assert.equal (Just 510510) (euler69 1_000_000)
module Euler069 where
import Prelude
import Control.Monad.ST (ST, for, run)
import Data.Array (mapWithIndex, (..))
import Data.Array.ST (STArray, peek, poke, withArray)
import Data.Foldable (maximumBy)
import Data.Int (toNumber)
import Data.Maybe (Maybe(..), maybe)
import Data.Tuple (Tuple(..), fst, snd)
crosser :: forall h. Int -> STArray h Int -> ST h Unit
crosser n a =
for 2 n \i -> do
mvi <- peek i a
when (mvi == Just i) do
let u = 1 + n / i
for 1 u \j -> do
let l = j * i
mvj <- peek l a
maybe (pure false) (\vj -> do
let vjn = vj - vj / i
poke l vjn a) mvj
sieve :: Int -> Array (Tuple Int Number)
sieve n =
let ns = 0..n
phi = run (withArray (crosser n) ns)
f i p = Tuple i (if p == 0 then 0.0 else toNumber i / toNumber p)
in mapWithIndex f phi
euler69 :: Int -> Maybe Int
euler69 = map fst <<< maximumBy (comparing snd) <<< sieve