using namespace std;

#include <cstdio>
#include <vector>
#include <bitset>

#define II inline
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "pairs.in"
#define OUT "pairs.out"
#define VAL_MAX 1000000

typedef vector<int> VI;

int K(-1),N;
bitset< VAL_MAX > V,P;
VI A(VAL_MAX),C(VAL_MAX);

II void ciur()
{
	for(int i=2;i<VAL_MAX;++i)
	{
		if(C[i])
			continue;
		for(int j=i;j<VAL_MAX;j+=i)
			if(P[j] == false)
				++C[j];
		
		if(i > 1000)
			continue;
		for(int j=i*i;j<VAL_MAX;j+=i*i)
			P[j] = true;
	}

	for(int i=2;i<VAL_MAX;++i)
	{
		if(P[i] == true)
			continue;
		for(int j=i;j<VAL_MAX;j+=i)
			if(V[j] == true)
				++A[i];
	}
}
	
II void scan()
{
	int x;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d",&N);
	FOR(i,1,N)
		scanf("%d",&x),
		V[x] = true;	
}

II ll solve()
{
	ll rez( (N*(N-1)) >> 1);
	FOR(i,2,VAL_MAX)
	{
		if(A[i] < 2)
			continue;
		if(C[i] & 1)
		{
			rez -= (ll) (A[i] * (A[i]-1)) / 2;
			continue;
		}
		rez += (ll) (A[i] * (A[i]-1)) / 2;
	}	
	return rez;
}

int main()
{
	scan();
	ciur();
	printf("%lld\n", solve() );
	return 0;
}