#include <stdio.h>
#include <stdlib.h>


bool e[1000005];
char c[800001];
int b[1000004];
int maxim=0;
void parsare(FILE *f1)
{
	int x=0,i;
	fread(c,800001,1,f1);
	for(i=1;c[i];i++)
		if(c[i]=='\n')
		{
			e[x]=true;
			if(x>maxim)
				maxim=x;
			x=0;
		}
		else
			x=10*x+c[i]-'0';
	e[x]=true;
	if(x>maxim)
		maxim=x;
}
void ciur()
{
	int i,j;
	b[1]=true;
	for(i=2;i*i<=1000000;i++)
		if(b[i]==0)
			for(j=i;j<=1000000;j=j+i)
				if(b[j]!=-1)
				{
					b[j]++;
					if((j/i)%i==0)
						b[j]=-1;
				}
}
int main()
{
	int i,j,bar,n,copiei,nr,div,a;
	long long d=0;
	FILE *f1,*f2;
	f1=fopen("pairs.in","r");
	f2=fopen("pairs.out","w");
	fscanf(f1,"%d",&n);
	parsare(f1);
	ciur();
	for(i=2;i<=maxim;i++)
	{
		div=0;
		if(b[i]==-1)
			continue;
		else
			for(j=i;j<=maxim;j=j+i)
				if(e[j])
					div++;
		if(b[i]%2==1)
			d=d+div*(div-1)/2;
		else
			d=d-div*(div-1)/2;

	}
	d=n*(n-1)/2-d;
	fprintf(f2,"%d",d);
	fclose(f1);
	fclose(f2);

	return 0;
}