この記事は ひとりアドベントカレンダーRosettaCodeで楽しむプログラミング Advent Calendar 2025の16日めの記事です。
タスク
指定された個数 n の異なる素数で、その和が指定された整数 x になるものを見つける。
複数の方法があるときは、極力小さい素数を使うものを示すこと。
考える
0～n個の素数の和で合計が y になる組み合わせ、というDPでもするのかと思ったけれど、そんなに難しく考えなくとも、単純に深さ優先探索で降りていけばできそうだ。
import Text.Printf
import Data.List
import Data.Numbers.Primes
import Control.Monad
search :: Int -> Int -> [Int] -> Maybe [Int]
search x 1 (p:_ ) = if p <= x && isPrime x then Just [x] else Nothing
search x k (p:ps)
| x <= p = Nothing
| otherwise = fmap (p :) (search (x - p) (pred k) ps) `mplus` search x k ps
main :: IO ()
main = forM_ test $ \(x,k) ->
case search x k primes of
Nothing -> printf "Partitioning %5d with %2d primes: is not possible\n" x k
Just ps -> printf "Partitioned %5d with %2d primes: %s\n" x k (intercalate "+" $ map show ps)
where
test = [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)] ++
[(22699, i) | i <- [1 .. 4]] ++ [(40355, 3)]
ghci> main
Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: (not possible)
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213
(0.06 secs, 25,783,088 bytes)
最後の一つになったら、それが素数で、まだ使ってよいものならOK、さもなくば失敗。
複数個の素数を使うとき、素数リストの先頭 p を引いてまだ数が残る必要がある。
p を使って残りを再帰でするか、使わずに再帰するかの2通りに分岐する。
出力のお化粧含めても、ページ中のどれよりもすっきりとまとまったコードになっていると思う。
Haskell版のも含めて。
ていうかJはもっと簡潔に書けるでしょ絶対。知らんけど。
今日は小ネタでした。