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


bool e[1000005];
char c[800001];
bool 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()
{
	b[1]=true;
	for(int i=2;i*i<=1000000;i++)
		if(!b[i])
			for(int j=i*i;j<=1000000;j=j+i)
				b[j]=true;
}
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++)
	{
		copiei=i;
		nr=0;
		div=0;
		bar=1;
		for(j=2;j*j<=i;j++)
		{
			if(!b[j] && copiei%j==0)
				if((copiei/j)%j!=0)
				{
					copiei=copiei/j;
					nr++;
				}
				else
				{	bar=0;
					break;
				}
			if(copiei==1)
				break;
		}
		if(bar)
			for(j=i;j<=maxim;j=j+i)
				if(e[j])
					div++;
		if(bar)
			if(nr==0)
				nr=1;
		if(nr%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;
}