F001B. La Conjectura de Goldbach P72452

L’any 1742, els matemàtics Leonard Euler i Christian Goldbach van intercanviar-se cartes on comentaven que qualsevol nombre parell més gran o igual que quatre es pot escriure com la suma de dos nombres primers. Aquesta propietat, anomenada la Conjectura de Goldbach, encara no s’ha pogut demostrar ni desmentir, malgrat haver passat més de 260 anys. Tantmateix, amb ordinadors s’ha demostrat que és certa per als nombres fins a 10¹⁴.

Implementeu una acció

que escrigui cada parella de nombres primers p i q amb p ≤ q tal que p + q = |n|. Com a precondició, teniu que |n| és parell i que 4 ≤ |n| ≤ 100000.

Per ajudar-vos a resoldre aquest exercici, la capçalera inclou dos paràmetres addicionals: El vector |v| conté en ordre els 9592 nombres primers més petits que 100000. El seu contingut és:

||

||

L’enter |j| indica la posició dins de |v| del màxim de tots els primers més petits que |n|. Per exemple, si |n| = 4, |j| = 1; si |n| = 6, |j| = 2; si |n| = 8 o |n| = 10, |j| = 3; …; si |n| està entre 99972 i 99988, |j| = 9589; si |n| = 99990, |j| = 9590; i si |n| està entre 99992 i 100000, |j| = 9591.

Per resoldre aquest exercici no us cal entendre el programa principal, el qual ja se us dóna implementat; no el canvieu. Aquest precalcula unes taules amb informació per cridar la vostra acció |goldbach()| amb els paràmetres adequats per a cadascun dels nombres llegits.

Entrada

L’entrada és una seqüència de naturals parells entre 4 i 100000 (ambdós inclosos).

Sortida

Per a cada |n|, cal escriure el nombre |n| seguit de ‘|=|’. A continuació, amb un ‘|+|’ enmig i separades per comes, cal escriure cadascuna de les diferents parelles de nombres primers p i q amb p ≤ q que sumen |n|. Les parelles s’han d’escriure en ordre creixent respecte de p. Seguiu el format de l’exemple.

Observació

El programa que comprovi si p + q = |n| per a cada parella de primers p i q amb p ≤ q < |n|, serà rebutjat pel Jutge per ser massa lent.