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 Setter:

Bakhtiar Hasan

Please login to submit solution to this problem.

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

Problem Stats

84/207

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 kpretomazi Cpp 0.00s
06 feodorv Cpp14 0.00s
07 SakibAlamin Cpp14 0.00s
08 hmtanbir Cpp14 0.00s
09 mh755628 Cpp 0.00s
10 abdulmukit Cpp 0.01s
11 Morass Cpp14 0.01s
12 avivilla Cpp14 0.01s
13 ____ Cpp14 0.01s
14 CodeSlayerOmega Cpp14 0.01s
15 anik_JU Cpp14 0.01s
16 sumit1993 Cpp14 0.01s
17 hrOarr Cpp14 0.01s
18 seyedssz Cpp14 0.01s
19 Rajan_sust Cpp14 0.01s
20 asma_chy Cpp14 0.01s
21 onucsecu Cpp14 0.01s
22 tariqiitju Cpp 0.01s
23 sazal_dev Cpp14 0.01s
24 Mr_adnan Cpp14 0.01s
25 Masum_ice Cpp14 0.01s
26 zyyxxx Cpp14 0.01s
27 Zeronfinity Cpp14 0.01s
28 xpo6 Cpp14 0.01s
29 murad_al_wajed Cpp14 0.01s
30 anowar1112 Cpp14 0.01s
31 alamin39 Cpp14 0.01s
32 badhansen123 Cpp14 0.01s
33 ahqmrf Cpp14 0.01s
34 ssavi Cpp14 0.01s
35 haasib Cpp14 0.01s
36 mahmud2690 Cpp 0.01s
37 smriad Cpp 0.01s
38 ikaadil Cpp 0.01s
39 Robbinb1993 Cpp 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 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

Your feedback is our precious!



Or call +88 02 9853138 for support