#include <cstdio>
#define NRMAX 1000005
#define NMAX 100005
using namespace std;

int n,k,Max;
int prim[NMAX],nr[NRMAX],v[NMAX];
bool viz[NRMAX];

void ciur()
{
    prim[1]=2;k=1;
    for(int i = 2; i*2 <= Max; ++i) viz[i*2]=1;
    for(int i = 3; i <= Max; i += 2)
    {
        if (viz[i] == 0)
        {
            prim[++k]=i;
            for(int j = 3; i * j <= Max; j += 2) viz[i*j]=1;
        }
    }
}

int main()
{
    freopen("pairs.in","r",stdin);
    freopen("pairs.out","w",stdout);
    scanf("%d",&n);
    Max = 0;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&v[i]);
        if (v[i] > Max) Max = v[i];
    }

    ciur();

    for(int i = 1; i <= n; ++i)
    {
        int x = v[i];
        int j = 1;
        while(x > 1)
        {
            if (viz[x] == 0 && x%2 != 0) {++nr[x];break;}
            if (x % prim[j] == 0)
            {
                ++nr[prim[j]];
                while(x % prim[j] == 0) x /= prim[j];
            }
            ++j;
        }
    }

    long long sol = (1ll * n * (n-1)) / (2 * 1ll);
    for(int j = 2; j <= Max; ++j)
    {
        sol -= ((1ll * nr[j] * (nr[j]-1) / (2 * 1ll)));
    }
    printf("%lld\n",sol);
    return 0;
}