In 1742, the mathematicians Leonard Euler and Christian Goldbach
exchanged letters where they claimed
that an even number greater or equal than four
can be written as a sum of two odd numbers.
This property, called Goldbach’s conjecture, has still neither
been proved nor disproved, despite of it happened 260 years ago.
However, using computers, it has been proved that Goldbach’s conjecture
is true for numbers less than 10^{14}.

Implement a procedure

that prints each pair of odd numbers *p* and *q* with *p* ≤ *q*
such that *p* + *q* = |n|.
As preconditions, we know that |n| is an even number and that 4 ≤ |n| ≤ 100000.

In order to help you solving this problem, the header includes two additional parameters: Vector |v| contains, in order, the first 9592 prime numbers less than 100000. Its content is:

||

||

0 | 1 | 2 | 3 | 4 | … | 9588 | 9589 | 9590 | 9591 |

2 | 3 | 5 | 7 | 11 | … | 99961 | 99971 | 99989 | 99991 |

Integer |j| indicates the position in |v| of the maximal odd number less than |n|. For instance, if |n| = 4, |j| = 1; if |n| = 6, |j| = 2; if |n| = 8 or |n| = 10, |j| = 3; …; if |n| is between 99972 and 99988, |j| = 9589; if |n| = 99990, |j| = 9590; and if |n| is between 99992 and 100000, |j| = 9591.

You do not need to understand the main program, which is already implemented; do not modify it. It calculates some tables with information to call your |goldbach()| with the suitable parameters for each read number.

**Input**

The input is a sequence of natural even numbers between 4 and 100000 (both included).

**Output**

For each |n|,
you must write the number |n| followed by ‘|=|’.
Afterwards, with a ‘|+|’ sign between and separated by commas,
you must write each different pair of prime numbers
*p* and *q* with *p* ≤ *q* whose sum is |n|.
You must write the pair in increasing order with regard to *p*.
Follow the format of the instance.

**Observation**

The program that checks if *p* + *q* = |n|
for each pair of prime numbers *p* and *q* with *p* ≤ *q* < |n|,
will be rejected for being too much slow.

Public test cases

**Input**

48 38 12 100 4

**Output**

48 = 5+43, 7+41, 11+37, 17+31, 19+29 38 = 7+31, 19+19 12 = 5+7 100 = 3+97, 11+89, 17+83, 29+71, 41+59, 47+53 4 = 2+2

Information

- Author
- Professorat de P1
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++