#include <stdio.h>
#include <math.h>

#define MILION 1000002
#define SUTAMII 100002


int n,i,j,t,x,d,max,np,res,aux,ok;
int ap[MILION];
int prim[SUTAMII];
int p[SUTAMII];
int a[MILION];
int nr[MILION];


int main(){
  FILE *f = fopen("pairs.in","r");
  fscanf(f,"%d",&n);
  for (i=1;i<=n;i++) {
    fscanf(f,"%d",&nr[i]);
    if (nr[i]>max)
      max=nr[i];
    ap[nr[i]]=1;
  }
  fclose(f);

  for (i=2;i<=max;i++)
    for (j=i;j<=max;j+=i)
      if (ap[j])
	a[i]++;

  for (i=2;i<=(int)sqrt(max);i++)
    if (p[i]==0)
      for (j=i+i;j<=(int)sqrt(max);j++)
	p[j]=1;

  np=0;
  for (i=2;i<=(int)sqrt(max);i++)
    if (p[i]==0)
      prim[++np]=i;

  res=0;
  for (i=2;i<=max;i++)
    if (a[i]>1){
      aux = i; d=1; x=0;
      ok=1;
      while (aux!=1) {
	t=0;
	while (aux%prim[d]==0) {
	  aux/=prim[d];
	  t++;
	}
	if (t>1) {
	  ok=0;
	  break;
	}
	if (t==1)
	  x++;
	d++;
	if (d>np) break;
      }
      if (ok&&(aux!=1))
	x++;
      if (ok) {
	if (x%2==1)
	  res+=((a[i])*(a[i]-1)/2);
	else
	  res-=((a[i])*(a[i]-1)/2);
      }
    }




  FILE *g = fopen("pairs.out","w");
  fprintf(g,"%d",n*(n-1)/2-res);
  fclose(g);
  return 0;
}