# DCP-177: Modified Golbach's Conjecture Back to All Problems

Medium Divide and Conquer > Dynamic Programming

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory. It states: > Every even integer greater than 2 can be expressed as the sum of two primes. The conjecture has been shown to hold up through **4 X 10<sup>18</sup>**, but remains unproven despite considerable effort. Let's modify this one a little bit. Let's say, > Any number greater than 2 can be written as sum of 1 or more primes. Now you are given the task to check this conjecture. You have to find out if a number **N** can be written as sum of 1 or more primes. A bit too easy, eh? Ok, let's make it more difficult(!). You need to find out, in how many ways the number **N** can be written as sum of 1 or more primes. Input: ------ Input starts with an integer **T (1 ≤ T ≤ 100)**, denoting the number of test cases. Each case contains an integer **N (2 ≤ N ≤ 1000)**. Output: ------- For each case of input, you need to print the case number, followed by the number of ways. If **N** can't be written in such way, print **"Wrong"** (without the quotation marks). Sample Input ------------ 2 5 10 Sample Output ------------- Case 1: 2 Case 2: 5

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 3.00 Go 3.00 Java 3.00 JavaScript 3.00 Objective-C 3.00 Perl 3.00 PHP 3.00 Python 3.00 Python3 3.00 Ruby 3.00 VB.Net 3.00

# 85/208

Solve/Submission

### Ranking

# User Language Timing
01 swapnilsaha Cpp14 0.00s
02 Najat Cpp14 0.00s
03 sakib_muhit Cpp14 0.00s
04 a_rahman Cpp14 0.00s
05 hmtanbir Cpp14 0.00s
06 feodorv Cpp14 0.00s
07 SakibAlamin Cpp14 0.00s
08 kpretomazi Cpp 0.00s
09 mh755628 Cpp 0.00s
10 mahmud2690 Cpp 0.01s
11 abdulmukit Cpp 0.01s
12 Robbinb1993 Cpp 0.01s
14 Morass Cpp14 0.01s
15 tariqiitju Cpp 0.01s
17 ahqmrf Cpp14 0.01s
19 anik_JU Cpp14 0.01s
20 onucsecu Cpp14 0.01s
22 hrOarr Cpp14 0.01s
23 Rajan_sust Cpp14 0.01s
24 alamin39 Cpp14 0.01s
25 avivilla Cpp14 0.01s
26 sumit1993 Cpp14 0.01s
27 sazal_dev Cpp14 0.01s
29 CodeSlayerOmega Cpp14 0.01s
30 ToErr Cpp14 0.01s
31 Masum_ice Cpp14 0.01s
32 haasib Cpp14 0.01s
33 seyedssz Cpp14 0.01s
34 anowar1112 Cpp14 0.01s
35 zyyxxx Cpp14 0.01s
36 Zeronfinity Cpp14 0.01s
37 ssavi Cpp14 0.01s
38 ____ Cpp14 0.01s
39 asma_chy Cpp14 0.01s
40 kamrulashraf Cpp14 0.02s
41 sonjoydabnath Cpp14 0.02s
42 ovis96 Cpp14 0.02s
43 Ansarul_14 Cpp14 0.03s
44 Aman_khan Cpp14 0.03s
45 emrul Cpp14 0.04s
46 7Mahfuz Cpp14 0.04s
47 Sarwar05 Cpp 0.05s
48 saurabh3240 Cpp14 0.07s
49 Alice_2 Cpp14 0.09s
50 Ishrak Cpp14 0.09s
Feedback