## ECOO '07 R3 P1 - Sum of Primes

View as PDF

Points: 7
Time limit: 2.5s
Memory limit: 256M

Problem type

Any natural number can be expressed as the sum of or odd primes. If itself is a prime, only one number is required.

However, because there are so many solutions for large composite , it is your task to find the solution where are prime, and where is as large as possible, or, if cannot be expressed as the sum of two primes, find the solution where are prime and where is as large as possible, followed by where is as large as possible.

#### Examples       is larger than and so, the required solution is In this case, is larger than , and so the required solution is The input contains numbers on separate lines. These numbers are less than and larger than . Write a program that will find the sum of primes for each of these numbers as described, and display the result as is shown in the sample below.

#### Sample Input

49
152029
90118
4565973
705510

#### Sample Output

49 = 13 + 17 + 19
152029 = 152029
90118 = 44987 + 45131
4565973 = 1521991 + 1521991 + 1521991
705510 = 352753 + 352757

• commented on Feb. 2, 2021, 6:31 p.m. edit 4

Could someone please take a look at my python submission? I am getting WA for the non-sample cases. I'm using a brute force algorithm that takes an upper bound for the smallest prime and searches for it by incrementing.

https://dmoj.ca/submission/3356368

*RESOLVED

• commented on July 22, 2019, 9:56 p.m.

Goldbach's conjecture was not proved. That is why it's a conjecture.

• commented on July 30, 2019, 10:52 a.m.

IIRC they proved that it holds for at least all • commented on Feb. 17, 2019, 10:28 a.m.

Shouldn't the output for 49 be: 49 = 2 + 47

If you can't express 49 as the sum of two primes, then you go on to try and find three primes. But you can find two primes. So it shouldnt be 13+17 + 19

• commented on Dec. 24, 2018, 12:54 p.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on March 30, 2018, 11:58 a.m.

My code seems to work offline but when I submitted it the solution checker says that it's wrong for both the second and third test cases. What is the issue with my code?

• commented on April 21, 2017, 10:50 a.m.

for the first test case isn't it supposed to be 49 = 2 + 47

• commented on April 21, 2017, 1:59 p.m.

let the first number as large as possible

• commented on May 1, 2017, 1:43 p.m. edited

But.. the problem statement implies that you should express as a sum of three primes only if you can't express it as a sum of two primes.
IDK tho

• commented on May 1, 2017, 7:35 p.m.

Any natural number can be expressed as the sum of or odd primes.

• commented on May 2, 2017, 1:49 p.m.

lmao rip
fair enough

• commented on Aug. 26, 2018, 4:42 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on April 9, 2017, 4:42 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on April 9, 2017, 6:40 p.m. isn't a prime number, and all of , and must be prime.