icyrock.com
HomePureScript solution to Project Euler problem 47
2021-Aug-01 22:08
Problem details at Project Euler problem 47 page.
Test
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 | module Euler047Test (euler47suite) where import Prelude import Data . List (fromFoldable) import Data . Maybe ( Maybe ( .. )) import Data . Set as S import Euler047 (divisors, euler47, findConsFac, primes) import Test . Unit (TestSuite, suite, test) import Test . Unit . Assert as Assert euler47suite :: TestSuite euler47suite = suite "Euler 47" do test "Warmup" do let ps = primes 646 pss = S . fromFoldable ps Assert . equal (fromFoldable [ 2 , 7 ]) (divisors ps pss 14 ) Assert . equal (fromFoldable [ 3 , 5 ]) (divisors ps pss 15 ) Assert . equal (fromFoldable [ 2 , 2 , 7 , 23 ]) (divisors ps pss 644 ) Assert . equal (fromFoldable [ 3 , 5 , 43 ]) (divisors ps pss 645 ) Assert . equal (fromFoldable [ 2 , 17 , 19 ]) (divisors ps pss 646 ) Assert . equal ( Just 14 ) (findConsFac 2 14 ) Assert . equal ( Just 644 ) (findConsFac 3 644 ) test "Real" do Assert . equal ( Just 134043 ) (euler47 unit) |
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | module Euler047 where import Prelude import Data . List (List( .. ), drop , filter , head , range, snoc) import Data . Maybe ( Maybe ( .. )) import Data . Set (Set, member) import Data . Set as S isPrime :: Int - > Boolean isPrime n = let go j | j * j > n = true | n `mod` j == 0 = false | otherwise = go (j + 1 ) in go 2 primes :: Int - > List Int primes n = filter isPrime $ range 2 n divisors :: List Int - > Set Int - > Int - > List Int divisors psi pss ni = let go ps n ks = case head ps of Nothing - > Nil Just j - > if j == n then ks `snoc` j else if n `member` pss then ks `snoc` n else if n `mod` j == 0 then go ps (n `div` j) (ks `snoc` j) else go ( drop 1 ps) n ks in go psi ni Nil isConsFac :: List Int - > Set Int - > Int - > Int - > Boolean isConsFac ps pss fc n = let fcnt = S . size <<< S . fromFoldable <<< divisors ps pss go j | j == n + fc = true | fcnt j < fc = false | otherwise = go (j + 1 ) in go n findConsFac :: Int - > Int - > Maybe Int findConsFac fc n = let ps = primes n pss = S . fromFoldable ps go j | j > n = Nothing | isConsFac ps pss fc j = Just j | otherwise = go (j + 1 ) in go 1 euler47 :: Unit - > Maybe Int euler47 _ = findConsFac 4 200000 |