ECOO '07 R3 P1 - Sum of Primes - Olympiads Online Judge

ECOO '07 R3 P1 - Sum of Primes

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 2.5s

Memory limit: 256M

Problem type

Any natural number $N > 4$ ~N > 4~ can be expressed as the sum of $1$ ~1~, $2$ ~2~ or $3$ ~3~ odd primes. If $N$ ~N~ itself is a prime, only one number is required.

However, because there are so many solutions for large composite $N$ ~N~, it is your task to find the solution $N = p + q$ ~N = p + q~ where $p \le q$ ~p \le q~ are prime, and where $p$ ~p~ is as large as possible, or, if $N$ ~N~ cannot be expressed as the sum of two primes, find the solution $N = p + q + r$ ~N = p + q + r~ where $p \le q \le r$ ~p \le q \le r~ are prime and where $p$ ~p~ is as large as possible, followed by where $q$ ~q~ is as large as possible.

Examples

$10$ ~10~	$49$ ~49~
$10 = 3 + 7$ ~10 = 3 + 7~	$49 = 13 + 13 + 23$ ~49 = 13 + 13 + 23~
$10 = 5 + 5$ ~10 = 5 + 5~	$49 = 13 + 17 + 19$ ~49 = 13 + 17 + 19~

$5$ ~5~ is larger than $3$ ~3~ and so, the required solution is $10 = 5 + 5$ ~10 = 5 + 5~.

In this case, $17$ ~17~ is larger than $13$ ~13~, and so the required solution is $49 = 13 + 17 + 19$ ~49 = 13 + 17 + 19~.

The input contains $5$ ~5~ numbers on $5$ ~5~ separate lines. These numbers are less than $10\,000\,000$ ~10\,000\,000~ and larger than $4$ ~4~. 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

Sample Output

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

Comments

-5

MstrPikachu commented on July 23, 2019, 1:56 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

2

Riolku commented on July 30, 2019, 2:52 p.m. ← edited →

IIRC they proved that it holds for at least all $N \le 10^{18}$ ~N \le 10^{18}~

-3

Heimdall commented on Feb. 17, 2019, 3:28 p.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

-1

Leon commented on Feb. 17, 2019, 4:07 p.m.

https://dmoj.ca/problem/ecoo07r3p1#comment-5127

-1

KevinWan commented on April 21, 2017, 2:50 p.m.

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

-3

Ken_Shi commented on April 21, 2017, 5:59 p.m.

let the first number as large as possible

-3

Paradox commented on May 1, 2017, 5:43 p.m. ← edited →

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

2

Phoenix1369 commented on May 1, 2017, 11:35 p.m.

Any natural number $N > 4$ ~N > 4~ can be expressed as the sum of $1,2$ ~1,2~ or $3$ ~3~ odd primes.

4

Paradox commented on May 2, 2017, 5:49 p.m.

lmao rip
fair enough

-10

ScriptKitty commented on Aug. 26, 2018, 8:42 p.m.

Sum of 1 2 or 3 odd primes.

This comment is hidden due to too much negative feedback. Show it anyway.

-16

mse387 commented on April 9, 2017, 8:42 p.m.

For the 49 test case, wouldn't the more correct output be 15 + 17 + 17?

This comment is hidden due to too much negative feedback. Show it anyway.

11

Xyene commented on April 9, 2017, 10:40 p.m.

$15$ ~15~ isn't a prime number, and all of $p$ ~p~, $q$ ~q~ and $r$ ~r~ must be prime.