時間制限:1000ミリ秒
メモリ制限:65536KB
連続した素数の和
問題
一部の正の整数は一つ以上の連続した素数の和として表すことができる。与えられた自然数はこのように表すとき、何通りで表すことができるだろうか。例えば、53は２通り(5 + 7 + 11 + 13 + 17 と 53)で表すことができる。41は３通り(2 + 3 + 5 + 7 + 11 + 13 と 11 + 13 + 17 と 41)である。3はただ一通り(3)でしか表すことができない。また、20はこのように表すことができない。
和は必ず連続した素数の和でなければならないことに留意してください。ゆえに、20を 7 + 13 や 3 + 5 + 5 + 7と表すのは不適当です。
あなたの課題は、与えられた正の整数について、このように表すとき、何通りで表すことができるかを表示するプログラムを書くことです。
入力
入力は各行に一つずつ正の整数が与えられる。整数は2以上20000以下である。入力の終わりは0で表される。
出力
出力は0以外のそれぞれの与えられた入力と対応していて、それぞれの行は与えられた整数の連続した素数を用いた表し方の総数を含む。それ以外には何も出力してはならない。
入力例
2 3 17 41 20 666 12 53 0
出力例
1 1 2 3 0 0 1 2
出典
Japan 2005