#include <fstream>
#include <cstring>
#include <cmath>
#define maxn 1000000
#define MAX 1000100
using namespace std;
int p,m,multime[300002],a[100002],n,prime[100002],rad;
long long prod,sol,divizori[1000002],x[MAX];
bool in[MAX],no[MAX];

void ciur()
{
	for(int i=2;i<=1000000;i++)
	if(!divizori[i])
	{
		prime[++p]=i;
		divizori[i]=1;
		for(int j=i+i;j<=1000000;j+=i) divizori[j]++;
	}
}
int main()
{
	int i,j;
	ifstream fi("pairs.in");
	ofstream fo("pairs.out");
	fi>>n;
	rad=(int)sqrt((double)n);
	sol=n*(n-1)/2;
	ciur();
	for(i=1;i<=n;i++) 
	{
		fi>>a[i];
		in[a[i]]=1;
	}
	for(i=2;i<=maxn;i++)
	for(j=i;j<=maxn;j+=i) 
		if(in[j]) x[i]++;
	for(i=1;i<=p and prime[i]<=rad;i++)
	for(j=1;prime[i]*prime[i]*j<=maxn;j++) 
	no[prime[i]*prime[i]*j]=1;
	for(i=2;i<=maxn;i++)
	if(divizori[i] and x[i]>1 and !no[i])
	{
		if(divizori[i]%2) sol-=x[i]*(x[i]-1)/2; else sol+=x[i]*(x[i]-1)/2;
	}
	fo<<sol<<"\n";
	return 0;
}