#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;
int ap[DIM],n,x,pr[DIM];
bool ok[DIM];
long long ans,nr,i,j;
int main()
{
    ifstream f ("pairs.in");
    ofstream g ("pairs.out");
    f>>n;
    for(i=1; i<=n; ++i)
    {
        f>>x;
        ap[x]=1;
    }
    for(i=2; i<DIM; ++i)
        if(!pr[i])
            for(j=i; j<DIM; j+=i)
                pr[j]++;
    for(i=2; i*i<DIM; ++i)
        for(j=i*i; j<DIM; j+=i*i)
            ok[j]=true;
    for(i=2; i<=DIM; ++i)
        if(!ok[i])
        {
            nr=0;
            for(j=i; j<DIM; j+=i)
                nr+=ap[j];
            if(pr[i]%2)ans+=(nr)*(nr-1);
            else ans-=nr*(nr-1);
        }
    g<<n*(n-1)/2-ans/2;
    return 0;
}