私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「素数の足し算で」（CodeIQ）を参照してください。
【概要】
整数を、ある範囲の相異なる素数の足し算で表現することを考えます。
例えば、39 を 3以上19以下の、相異なる素数のみを使った足し算で表現する方法は、
3+5+7+11+13
3+17+19
7+13+19
の3通りあります（つまり、順序が異なるだけのものは同一とみなします）。
「39」、「3〜19」 のような情報を与えますので、場合の数(この例だと 3)を計算するプログラムを書いてください。
【入出力】
入力は
39 3 19
のような感じです。
空白区切りで、合計、足し算に使う数の最小値、足し算に使う数の最大値 が並んでいます。
出力は、
3
のような感じで、普通に10進数で出力してください。
【例】
入力 出力 39 3 19 3 70 9 30 2 40 21 39 0
【補足】
不正な入力に対処する必要はありません。
合計は、1以上 100 以下の整数です。
足し算に使う数の最小値は 1 以上の整数で、足し算に使う数の最大値は最小値以上 100 以下の整数です。
ライブラリなどに素数の判定や列挙を行う関数などがある場合、遠慮なく使っていただいて構いません。
Rubyで解答しています。
#!/usr/bin/ruby
require 'prime'
def calc(sum, lst, now)
if now == sum then return 1
elsif now > sum then return 0
elsif lst.empty? then return 0
end
ret = 0
for i in 0...lst.size
nxt = now + lst[i]
ret += calc(sum, lst[i+1..-1], nxt)
end
return ret
end
def solve(sum, mn, mx)
lst = []
Prime.each(mx){|x| if x >= mn then lst << x end}
return calc(sum, lst, 0)
end
# main
while line = gets
line.strip!
if line.empty? then next end
sum, mn, mx = line.split.map{|a| a.to_i}
p solve(sum, mn, mx)
end
組み合わせの問題として見た場合、結構大変そうですが合計の最大が100なので素直にやれば大丈夫です。
まず素数のリストを作成します。
そのリストから任意の数を選びそれまでに選んだ数の合計が合計値になっているかをチェックします。
合計値になっていればカウントし、合計値を超えているか選べる素数が無くなっていたら終わります。そうでなければ選んだ数より大きい素数だけをリストに残し、同じことを繰り返します。
これで合計値になるパターンを列挙できます。
合計8、最小1、最大7の場合で具体的にやって見ます。
8以下の素数は[2,3,5,7]です。
最初に2を選んだ場合、合計は8未満なので次の数を選びます。選べる数には3、5、7があります。
(2,3)は5なので次の数を5、7から選びます。
(2,3,5)は10なのでダメです。
(2,3,7)は12なのでダメです。
(2,5)は7なので次の数を7から選びます。
(2,5,7)は14なのでダメです。
(2,7)は9なのでダメです。
最初に3を選んだ場合、次の数は5,7から選びます。
(3,5)は8でOKです。
(3,7)は10なのでダメです。
最初に5を選んだ場合、次の数は7から選びます。
(5,7)は12なのでダメです。
最初に7を選んだら8未満ですがもう素数が残っていないのでダメです。
整理すると次のようになり答えば1になります。
2+3+5=10 ×
2+3+7=12 ×
2+5+7=14 ×
2+7=9 ×
3+5=8 ○
3+7=11 ×
5+7=13 ×
7 ×
入力値を数値にしてsolve()に渡し、結果を印字します。
引数は入力値でsumが合計、mnが足し算に使う最小値、mxが足し算に使う最大値です。
最大値以下の素数を列挙し、solve()に渡して結果を求めます。solve()の第三引数はそれまでに選んだ数値の合計値なので初期値0を設定します。
引数sumは入力値の合計値、lstは使用可能な素数のリスト、nowはそれまでに選んだ素数の合計値です。
nowが合計値になっているかをチェックし、合計値に等しければ1、合計値を上回っているかlstに素数が残っていなかったら0を返します。それ以外の場合は次の数を選びます。
lstの残りから順に数値を選び、calc()を再帰的に呼び出します。引数は入力された合計値、lst中で現在選んだ値よりも大きいもの、nowに選んだ数を加えた値になります。
calc()がリターンしてきた時、合計値に等しければ1、そうでなければ0が帰ってくるのでそれを足し合わせればパターン数になります。
ぱっと見、組み合わせ数が大変なことになるかなと思ったのですが、考えているうちに最大100程度なら大したことが無いように思えたので素直にやって見たら予想通り時間的にも十分間に合いました。