# 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 SakibAlamin Cpp14 0.00s
05 kpretomazi Cpp 0.00s
06 a_rahman Cpp14 0.00s
07 hmtanbir Cpp14 0.00s
08 feodorv Cpp14 0.00s
09 mh755628 Cpp 0.00s
10 Robbinb1993 Cpp 0.01s
12 onucsecu Cpp14 0.01s
13 anik_JU Cpp14 0.01s
15 tariqiitju Cpp 0.01s
17 mahmud2690 Cpp 0.01s
18 abdulmukit Cpp 0.01s
19 ahqmrf Cpp14 0.01s
20 Morass Cpp14 0.01s
21 Rajan_sust Cpp14 0.01s
22 alamin39 Cpp14 0.01s
23 ____ Cpp14 0.01s
24 avivilla Cpp14 0.01s
25 asma_chy Cpp14 0.01s
27 anowar1112 Cpp14 0.01s
28 zyyxxx Cpp14 0.01s
29 Masum_ice Cpp14 0.01s
30 Zeronfinity Cpp14 0.01s
31 ssavi Cpp14 0.01s
32 haasib Cpp14 0.01s
33 seyedssz Cpp14 0.01s
34 sazal_dev Cpp14 0.01s
35 hrOarr Cpp14 0.01s
36 sumit1993 Cpp14 0.01s
37 xpo6 Cpp14 0.01s
38 CodeSlayerOmega 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 7Mahfuz Cpp14 0.04s
46 emrul Cpp14 0.04s
47 Sarwar05 Cpp 0.05s
48 saurabh3240 Cpp14 0.07s
49 dip_BRUR Cpp14 0.09s
50 Alice_2 Cpp14 0.09s
Feedback