e552: 01210 - Sum of Consecutive Prime Numbers
Tags : DP 區間問題 質數
Accepted rate : 48人/48人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-28 22:47

Content

有一些正整數可以由一個或多個連續質數之和表示。現在給你一個正整數,該正整數可以用多少種連續質數合來表示?
例如,整數53具有兩種表示(5 + 7 + 11 + 13 + 17)和(53)。
整數41具有三種表示(2 + 3 + 5 + 7 + 11 + 13)、(11 + 13 + 17)和(41)。
整數3僅具有一種表示形式,即(3)。
整數20沒有這種表示形式。
請注意,被加數必須是"連續"的質數,因此(7 + 13)或(3 + 5 + 5 + 7)都不是整數20的有效表示。
您的任務是寫一個程式判斷該正整數可以用多少種連續質數合來表示。

Input

輸入每一行有一個正整數n (2 <= n <= 10000),n代表需要判斷的正整數。
如果n = 0代表輸入結束。

Output

對於每組輸入,輸出該正整數可以用多少種連續質數合來表示。

Sample Input #1
2
3
17
41
20
666
12
53
0
Sample Output #1
1
1
2
3
0
0
1
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
Hint :
Tags:
DP 區間問題 質數
出處:
UVA [管理者:
ig99lp33lp33 (위즈원)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」