Jump to content

Partition an integer x into n primes: Difference between revisions

Partition an integer x into n primes (view source)

Revision as of 16:04, 3 May 2020

773 bytes removed ,  4 years ago
m
→‎{{header|Haskell}}: Used Data.Numbers.Primes, tidied.
(Added Prolog Solution)
m (→‎{{header|Haskell}}: Used Data.Numbers.Primes, tidied.)
Line 608:
 
=={{header|Haskell}}==
<lang haskell>{-#import LANGUAGEData.Bool TupleSections #-}(bool)
import Data.Numbers.Primes
 
import Data.List (delete, intercalate)
 
-- PRIME PARTITIONS ------------------------------------- PRIME PARTITIONS ---------------------
partition :: Int -> Int -> [Int]
partition x n
| n <= 1 =
[ x
| last psx == xlast ps ]
| otherwise = partition_go ps x n
where
ps = takeWhile (<= x) primes
partition_go ps_ x 1 =
[ x
| x `elem` ps_ ]
partition_go ps_ x n =
let found = foldMap partitionsFound ps_
in nullOrbool (head found) [] (headnull found)
where
partitionsFound p =
let r = x - p
rs = partition_go (delete p (takeWhile (<= r) ps_)) r (n - 1)
in nullOr rs []bool [p : rs] [] (null rs)
 
-- TEST ------------------------------------------- TEST ---------------------------
main :: IO ()
main =
mapM_ putStrLn $
(\(x, n) ->
(intercalate
" -> "
[ justifyLeft 9 ' ' (show (x, n))
, let xs = partition x n
in nullOr xs "(no solution)"bool (intercalate "+" (show <$> xs)) "(no solution)" (null xs)
])) <$>
concat
[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)]
, (22699, ) 22699 <$> [1 .. 4]
, [(40355, 3)]
]
 
-- GENERIC ------------------------------------------- GENERIC -------------------------
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)</lang>
 
nullOr
:: Foldable t1
=> t1 a -> t -> t -> t
nullOr expression nullValue orValue =
if null expression
then nullValue
else orValue
 
primes :: [Int]
primes =
2 :
pruned
[3 ..]
(listUnion
[ (p *) <$> [p ..]
| p <- primes ])
where
pruned :: [Int] -> [Int] -> [Int]
pruned (x:xs) (y:ys)
| x < y = x : pruned xs (y : ys)
| x == y = pruned xs ys
| x > y = pruned (x : xs) ys
listUnion :: [[Int]] -> [Int]
listUnion = foldr union []
where
union (x:xs) ys = x : union_ xs ys
union_ (x:xs) (y:ys)
| x < y = x : union_ xs (y : ys)
| x == y = x : union_ xs ys
| x > y = y : union_ (x : xs) ys</lang>
{{Out}}
<pre>(99809,1) -> 99809
Hout
9,659

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/274683"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information