În zorii zilei, harnicele albinuţe se pregătesc să zboare la cules de nectar. În apropierea stupului, se află o grădină fermecată cu N flori, numerotate 1, 2,… N. Pentru fiecare floare se cunoaște numărul de petale.

Anumite flori din grădină pot fi flori capcană. O astfel de floare are un număr prim de petale. Dacă o albină s-ar aşeza pe corola florii capcană, atunci floarea i-ar fura o cantitate de nectar egală cu numărul ei de petale.

Alte flori pot fi florile abundenţei. Numărul de petale ale florii abundenţei are un număr impar de divizori. Dacă o albină s-ar aşeza pe corola unei astfel de flori, atunci ea i-ar dărui albinuţei o cantitate de nectar egală cu triplul numărului ei de petale.

Celelalte flori pot fi flori obişnuite. Dacă o albină s-ar aşeza pe corola unei flori obişnuite, atunci floarea i-ar dărui albinuţei o cantitate de nectar egală cu numărul ei de petale.

Regina stupului, le-a poruncit albinuţelor să adune cea mai mare cantitate de nectar care se poate culege din grădină, altfel … vor fi alungate din stup.

Cerinţă

Scrieţi un program care să citească numerele naturale N și numărul de petale ale fiecărei flori şi care să determine cantitatea maximă C de nectar pe care albinuţele o pot aduna din grădina fermecată.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând numărul de petale ale fiecărei flori.

Date de ieșire

Programul va afișa pe ecran numărul C.

Restricții și precizări

• 1 ≤ n ≤ 100 000
• fiecare floare are cel mult 10 000 petale
• Nectarul unei flori poate fi cules de o singură albină.
• Cantitatea maximă C de nectar culeasă este un număr natural, C ≤ 2 000 000 000

Exemplu

Intrare

8
25 13 10 7 1 12 31 102

Ieșire

202

Explicație

Cantitatea maximă de nectar se obţine din florile 1, 3, 5, 6 şi 8. C=3x25+10+3x1+12+102=202

#include <bits/stdc++.h>

using namespace std;

int prim(int n)
{
    int d=2;
    int cnt=1;
    while(n>1)
    {
        int p = 0;
        while(n%d==0)
        {
            n/=d;
            p++;
        }
        cnt*=(p+1);
        d++;
        if(d*d>n)
        d=n;
    }
    if(cnt==2)
    return 1;
    else
    return 0;
}

int main()
{
    int n;
    cin >> n;
    int x;
    int s=0;
    for(int i = 0 ; i < n ; ++i)
    {
        cin >> x;
        int m=sqrt(x);
        if(m*m==x)
        s+=3*x;
        else if(prim(x))
        s+=0;
        else
        s+=x;
    }
    cout << s;
}