F013B. Codificació de Gödel P41073


Statement
 

pdf   zip

thehtml

[r] Considereu la seqüència infinita de nombres primers: p0 = 2, p1 = 3, p2 = 5, etcètera. Per a cada nombre s de n xifres s = sos1… sn−1, la seva codificació de Gödel es defineix com

 
∏
0 ≤ i < n
 pisi ⁠ ⁠ = ⁠ ⁠ p0s0 · p1s1 … pn−2sn−2 · pn−1sn−1

Per exemple, la codificació de Gödel de 4031 és 24 · 30 · 53 · 71 = 16 · 1 · 125 · 7 = 14000.

Feu un programa que llegeixi nombres i escrigui la seva codificació de Gödel.

Entrada

L’entrada consisteix en diversos nombres, amb possibles zeros a l’esquerra. Els nombres primers necessaris per a les codificacions dels nombres donats són tots més petits que 4 · 106.

Sortida

Per a cada nombre de l’entrada, cal escriure una línia amb aquell nombre i la seva codificació, seguint el format de l’exemple. Suposeu que les codificacions no tindran mai sobreeiximents.

Observacions

Alguns dels nombres donats seran molt llargs, o tindran zeros a l’esquerra. Feu servir strings per llegir i tractar aquests nombres. A més, el vostre programa ha de ser eficient. Useu el garbell d’Eratòstenes per calcular tots els primers fins a 4 · 106 al principi del programa.

Public test cases

  • Input

    4031
010
101
808
00
00000001
11111111
10301040
0
1
9
20200000000000000000000000000012

    Output

    4031 -> 14000
010 -> 3
101 -> 10
808 -> 100000000
00 -> 1
00000001 -> 19
11111111 -> 9699690
10301040 -> 229682750
0 -> 1
1 -> 2
9 -> 512
20200000000000000000000000000012 -> 217944700
    • Information
    Author
    Professorat de P1
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++