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 1<<20

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

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