F001B. La Conjectura de Goldbach P72452


Statement
 

pdf   zip

thehtml

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

Implementeu una acció

void goldbach(int n, const vector<int>& v, int j);

que escrigui cada parella de nombres primers p i q amb pq 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:

||

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

  2  3  5  7  11  …99961999719998999991

||

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 pq 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 pq < |n|, serà rebutjat pel Jutge per ser massa lent.

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
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++