Suma de productes de factors primers P97297


Statement
 

pdf   zip

thehtml

Donat un natural n ≥ 2, sigui L(n) la llista ordenada dels factors primers d’n. Per exemple, L(105) = [3, 5, 7] i L(40) = [2, 2′, 2″, 5]. (Distingim els dosos per claredat en l’explicació que segueix.)

Definim S(n) com la suma de tots els productes de parells de factors primers dins d’L(n). Formalment, si hi ha fn factors primers dins d’L(n),

S(n) = 
 
∑
1 ≤ i < fn
   
 
∑
i < j ≤ fn
 L[i] · L[j] ⁠ ⁠ .

Per exemple,

S(105) = 3 · 5 + 3 · 7 + 5 · 7 = 15 + 21 + 35 = 71 ⁠ ⁠ ,
S(40) = 2 · 2′ + 2 · 2″ + 2 · 5 + 2′ · 2″ + 2′ · 5 + 2″ · 5 = 4 + 4 + 10 + 4 + 10 + 10 = 42 ⁠ ⁠ .

Fixeu-vos que, per definició, S(n) = 0 per a tot primer n.

Podeu calcular S(n) eficientment?

Entrada

L’entrada consisteix en diverses n, totes entre 2 i 109.

Sortida

Escriviu la S(n) corresponent a cada n donada.

Public test cases

  • Input

    105
40
7
4
2
999999937
1000000000

    Output

    S(105) = 71
S(40) = 42
S(7) = 0
S(4) = 4
S(2) = 0
S(999999937) = 0
S(1000000000) = 1854
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++