# F001B. Goldbach's Conjecture P72452

Statement html

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 1014.

Implement a procedure

that prints each pair of odd numbers p and q with pq 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 pq 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 pq < |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++