Ghiţă s-a hotărât să plece de-acasă de Ignat, având nişte previziuni sumbre. Neavând bani, s-a gândit să-şi scoată un single de sezon, “guIT”. Din vânzarea lui a obţinut frumoasa sumă de n dolari.

Cerința

Pentru a câştiga un meniu vegetarian de Crăciun, trebuie să aflaţi suma numerelor prime din descompunerea lui n, ştiind că n este produs de trei numere prime distincte.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând suma celor trei numere prime din descompunerea lui n.

Restricții și precizări

• 1 ≤ n ≤ 10 12

Exemplu

Intrare

105

Ieșire

15

Explicație

105 = 3•5•7, deci suma este 3+5+7=15.

#include <bits/stdc++.h>


using namespace std;

int main()
{
    long long int n;
    cin >> n;
    long long int s=0;
    long long int d=2;
    while(n>1)
    {
        int p = 0;
        while(n%d==0)
        {
            n/=d;
            p++;
        }
        if(p>0)
        {
            s+=d;
        }
        d++;
        if(d*d>n)
            d=n;
    }
    cout << s;
    return 0;
}