# 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
11 mahmud2690 Cpp 0.01s
12 abdulmukit Cpp 0.01s
13 tariqiitju Cpp 0.01s
15 Robbinb1993 Cpp 0.01s
16 Morass Cpp14 0.01s
17 ahqmrf Cpp14 0.01s
19 anik_JU Cpp14 0.01s
20 onucsecu Cpp14 0.01s
22 Zeronfinity Cpp14 0.01s
23 ssavi Cpp14 0.01s
24 Rajan_sust Cpp14 0.01s
25 alamin39 Cpp14 0.01s
26 avivilla Cpp14 0.01s
27 sumit1993 Cpp14 0.01s
28 hrOarr Cpp14 0.01s
29 sazal_dev Cpp14 0.01s
31 CodeSlayerOmega Cpp14 0.01s
32 xpo6 Cpp14 0.01s
33 Masum_ice Cpp14 0.01s
34 haasib Cpp14 0.01s
35 seyedssz Cpp14 0.01s
36 anowar1112 Cpp14 0.01s
37 zyyxxx Cpp14 0.01s
38 ____ Cpp14 0.01s
39 asma_chy Cpp14 0.01s
40 sonjoydabnath Cpp14 0.02s
41 kamrulashraf 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 rajdipsaha Cpp14 0.09s
50 dip_BRUR Cpp14 0.09s
Feedback