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

Bakhtiar Hasan

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 |

Solve/Submission

# | 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 |

13 | ikaadil | Cpp | 0.01s |

14 | Morass | Cpp14 | 0.01s |

15 | tariqiitju | Cpp | 0.01s |

16 | smriad | Cpp | 0.01s |

17 | ahqmrf | Cpp14 | 0.01s |

18 | badhansen123 | Cpp14 | 0.01s |

19 | anik_JU | Cpp14 | 0.01s |

20 | onucsecu | Cpp14 | 0.01s |

21 | murad_al_wajed | 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 |

28 | Mr_adnan | 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 |

Copyright © 2015-2016 Dev Skill.

Feedback
#### Your feedback is our precious!

## Thank you for providing feedback! Our developers will be happy :)

## Sorry there was a problem when submitting the feedback. Please try again. :(