#include <stdio.h>
#include <string.h>

#define FIN "pairs.in"
#define FOUT "pairs.out"
#define MAX 1000100

int N,max,vec_ap[MAX],nr[MAX];
int prim[MAX];
long long REZ;
int i,j,l,x;

void ciur()
{

for (i=2;i<=max;++i)
     prim[i]=1;
for (i=2;i<=max;++i)
    {
     for (j=i+i;j<=max;j+=i)
	  if (vec_ap[j]==1)
	      vec_ap[i]++;
	  if (prim[i]==1)
	      {
	      nr[i]=1;
	      for (l=i+i;l<=max;l+=i)
		  {
		   prim[l]=0;
		   if ((l/i)%i!=0)
		       nr[l]++;
		    }
		}
      }
}



int maxim(int a, int b)
{

if (a>b) return a;
    else return b;
}


void read()
{

freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);

scanf("%d", &N);

max=0;

for (i=1;i<=N;++i)
     {
      scanf("%d", &x);
      max=maxim(max,x);
      //memset(vec_ap,0,sizeof(vec_ap));
      vec_ap[x]++;
      }
}



void solve()
{

read();
ciur();
REZ=N*(N-1)/2;
for (i=2;i<=max;++i)
     {
      if (nr[i]%2==0)
	 REZ+=vec_ap[i]*(vec_ap[i]-1)/2;
	 else
	 REZ-=vec_ap[i]*(vec_ap[i]-1)/2;
       }
printf("%lld", REZ);
}

int main()
{
solve();
return 0;
}