#include <stdio.h>
#include <stdlib.h>
#define nmax 100001
#define pmax 78500
// 2..1000000 -> 78498 prime numbers
long a[nmax],c[pmax],nc,max,p[500005],poz[500005],np,i,y;
long *v2[nmax],v[nmax];
long long nr,n;

void prim(long x);
void prim2(long x);
FILE *f,*g;
int main()
{
  long j,k,x;
  f=fopen("pairs.in","rt");
  g=fopen("pairs.out","wt");
  fscanf(f,"%lld\n",&n);
  max=0;
  for (i=1;i<=n;i++)
    {
      fscanf(f,"%ld\n",&a[i]);
      if (a[i]>max)
        max=a[i];
    }
  nr=n*(n-1)/2;
  nc=2;
  c[1]=2;
  c[2]=3;
  max/=2;
  for (i=5;i<=max;i+=2)
    {
      k=1;
      for (j=2;c[j]*c[j]<=i;j++)
        if (i%c[j]==0)
          {
            k=0;
            break;
          }
      if (k)
        c[++nc]=i;
    }
  for (i=1;i<=n;i++)
    {
      x=a[i];
      if (x!=1)
        prim(x);
    }
  for (i=1;i<=np;i++)
    v2[i]=(long *)calloc(v[i],sizeof(long));
    
  for (i=1;i<=np;i++)
    {
      poz[p[i]]=0;
      p[i]=0;
    }
  np=0;

  for (i=1;i<=n;i++)
    {
      x=a[i];
      if (x!=1)
        prim2(x);
    }

  for (i=1;i<=np;i++)
    {
      nr-=v2[i][0]*(v2[i][0]-1)/2;
      for (j=i-1;j>=1;j--)
       if (v2[j][0]>1)
        {
          y=0;
          for (k=1;k<=v2[j][0];k++)
            if (v2[j][k]%p[i]==0)
              y++;
          nr+=y*(y-1)/2;
        }
    }
  fprintf(g,"%lld\n",nr);
  fclose(f);
  fclose(g);
  return 0;
}

void prim(long x)
{
  int j;
  for (j=1;c[j]*c[j]<=x;j++)
    if (x%c[j]==0)
      {
        while (x%c[j]==0)
          x/=c[j];
        if (!poz[c[j]])
          {
            np++;
            poz[c[j]]=np;
            p[np]=c[j];
            v[np]+=2;
          }
         else
          {
            v[poz[c[j]]]++;//=(long *)calloc,(1,sizeof(long));
            //v[poz[c[j]]][++v[poz[c[j]]][0]]=a[i];
          }
      }
  if (x>1)
  if (!poz[x])
    {
      np++;
      poz[x]=np;
      p[np]=x;
      v[np]+=2;//=(long *)calloc(3,sizeof(long));
//      v[np][0]=1;
//      v[np][1]=a[i];
    }
     else
    {
      v[poz[x]]++;//=(long *)calloc(1,sizeof(long));
//      v[poz[x]][++v[poz[x]][0]]=a[i];
    }
      
}

void prim2(long x)
{
  int j;
  for (j=1;c[j]*c[j]<=x;j++)
    if (x%c[j]==0)
      {
        while (x%c[j]==0)
          x/=c[j];
        if (!poz[c[j]])
          {
            np++;
            poz[c[j]]=np;
            p[np]=c[j];
            v2[np][0]=1;
            v2[np][1]=a[i];
          }
         else
          {
            v2[poz[c[j]]][++v2[poz[c[j]]][0]]=a[i];
          }
      }
  if (x>1)
  if (!poz[x])
    {
      np++;
      poz[x]=np;
      p[np]=x;
      v2[np][0]=1;
      v2[np][1]=a[i];
    }
     else
    {
      v2[poz[x]][++v2[poz[x]][0]]=a[i];
    }
      
}