#include <fstream>
#include <cstring>

#define maxM 1000001

using namespace std;

bool v[maxM];
long long x[maxM];
int d[maxM];
bool p[maxM];

ifstream in;
ofstream out;

int main()
{
    int N,w,max=0;

    in.open("pairs.in");

    in>>N;

    memset(v,false,sizeof(v));
    for(int i=1;i<=N;++i)
    {
        in>>w;
        if(w>max) max=w;
        v[w]=true;
    }

    in.close();

    memset(x,0,sizeof(x));
    memset(d,0,sizeof(d));
    memset(p,true,sizeof(p));

    for(int i=2;i<=max;++i)
        for(int j=i;j<=max;j+=i)
            if(v[j])
            {
                ++x[i];
                if(j%(i*i)==0) p[j]=false;
            }

    for(int i=2;i<=max;++i)
        if(d[i]==0)
        {
            d[i]=1;
            for(int j=i+i;j<=max;j+=i)
                ++d[j];
        }

    long long sol=N*(N-1)/2;

    for(int i=2;i<=max;++i)
        if(x[i]>1&&p[i])
        {
            if(d[i]%2==1) sol-=x[i]*(x[i]-1)/2;
            else sol+=x[i]*(x[i]-1)/2;
        }

    out.open("pairs.out");

    out<<sol<<'\n';

    out.close();

    return 0;
}