Partition an integer x into n primes: Difference between revisions
Added a Haskell example, put languages in alpha sorted order
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: DRY, minor variable name tweaking, better 1 part fail example) |
(Added a Haskell example, put languages in alpha sorted order) |
||
Line 33:
<br><br>
=={{header|Haskell}}==
<lang haskell>import Data.List (delete, intercalate)
-- PRIME PARTITIONS ----------------------------------------------------------
partition :: Int -> Int -> [Int]
partition x n
| n <= 1 =
[ x
| last ps == x ]
| otherwise = partition_ ps x n
where
ps = takeWhile (<= x) primes
partition_ ps_ x 1 =
[ x
| x `elem` ps_ ]
partition_ ps_ x n =
let found = foldMap partitionsFound ps_
in if null found
then []
else head found
where
partitionsFound p =
let r = x - p
rs = partition_ (delete p (takeWhile (<= r) ps_)) r (n - 1)
in if null rs
then []
else [p : rs]
-- TEST ----------------------------------------------------------------------
main :: IO ()
main =
mapM_ putStrLn $
(\(x, n) ->
(intercalate
" -> "
[ justifyLeft 9 ' ' (show (x, n))
, let xs = partition x n
in if null xs
then "(no solution)"
else intercalate "+" (show <$> xs)
])) <$>
concat
[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)]
, [\x -> (22699, x)] <*> [1 .. 4]
, [(40355, 3)]
]
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)
-- PRIME SEQUENCE ------------------------------------------------------------
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
(18,2) -> 5+13
(19,3) -> 3+5+11
(20,4) -> (no solution)
(2017,24) -> 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
(22699,1) -> 22699
(22699,2) -> 2+22697
(22699,3) -> 3+5+22691
(22699,4) -> 2+3+43+22651
(40355,3) -> 3+139+40213</pre>
=={{header|Perl 6}}==
{{works with|Rakudo|2017.02}}
<lang perl6>my @primes = 2, 3, 5, -> $p { ($p + 2, $p + 4 ... &is-prime).tail } ... *; # lazy infinite list of primes
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! [] } # short circuit for '1' partition
multi partition ( Int $number, Int $parts where * > 0 = 2 ) {
my @these = @primes[ ^( @primes.first: * > $number, :k ) ];
for @these.combinations($parts) -> @this { return @this if @this.sum == $number }
[]
}
# TESTING
for 18,2, 19,3, 20,4, 99807,1, 99809,1, 2017,24, 22699,1, 22699,2, 22699,3, 22699,4, 40355,3
-> $number, $parts {
say (sprintf "Partition %5d into %2d prime piece", $number, $parts),
$parts == 1 ?? ': ' !! 's: ', (join '+', partition $number, $parts) || 'not possible'
}</lang>
{{out}}
<pre>Partition 18 into 2 prime pieces: 5+13
Partition 19 into 3 prime pieces: 3+5+11
Partition 20 into 4 prime pieces: not possible
Partition 99807 into 1 prime piece: not possible
Partition 99809 into 1 prime piece: 99809
Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partition 22699 into 1 prime piece: 22699
Partition 22699 into 2 prime pieces: 2+22697
Partition 22699 into 3 prime pieces: 3+5+22691
Partition 22699 into 4 prime pieces: 2+3+43+22651
Partition 40355 into 3 prime pieces: 3+139+40213</pre>
=={{header|REXX}}==
Line 99 ⟶ 215:
partitioned 40355 into 3 primes: 3+139+40213
</pre>
=={{header|zkl}}==
| |||