#include<cstdio>
using namespace std;
int maxi,val,n,smn,i,j,nr,pr[1009],cr[1009],s[1000009];
char ap[1000009];
long long cat,rez;
int main()
{
freopen("pairs.in","r",stdin);
freopen("pairs.out","w",stdout);
for(i=2;i<=1000;i++)
    if(cr[i]==0)
    {
        pr[++nr]=i;
        for(j=i*i;j<=1000;j+=i)
            cr[j]=1;
    }
scanf("%d",&n);
rez=(long long)1LL*n*(n-1)/2;
while(n)
{
    n--;
    scanf("%d",&val);
    ap[val]=1;
    if(val>maxi) maxi=val;
}
for(i=2;i<=maxi;i++)
    for(j=i;j<=maxi;j+=i)
        s[i]+=ap[j];
for(i=2;i<=maxi;i++)
{
    val=i;
    smn=0;
    for(j=1;pr[j]*pr[j]<=val;j++)
    if(val%pr[j]==0)
    {
        if(val%(pr[j]*pr[j])==0) break;
        smn^=1;
        while(val%pr[j]==0)
            val/=pr[j];
    }
    if(pr[j]*pr[j]<=val) continue;
    if(val>1) smn^=1;
    cat=(long long)s[i]*(s[i]-1)/2;
    if(smn==1) rez-=cat;
    else rez+=cat;
}
printf("%lld\n",rez);
return 0;
}