#include <stdio.h>

#define MAXN 100005
#define MAXV 1000005
#define MAXP 80000

int N, x[MAXN], MAX = 0;
long long NR;

char p[MAXV];
int primes[MAXP];
int prod[16];

int count[MAXV];

inline int gcd( int a, int b )
{
	for (; a % b; )
	{
		int c = a % b;
		a = b;
		b = c;
	}
	return b;
}

inline void back( int k, int K, int P, int l )
{
	if (P * prod[K - k] > MAX)
		return;

	if (k == K)
	{
		int curNr = 0;
		for (int j = P; j <= MAX; j += P)
			curNr += count[j];

		if (curNr <= 1)
			return;

		if (K & 1)
			NR -= ((long long)curNr * ((long long)curNr - 1)) >> 1;
		else
			NR += ((long long)curNr * ((long long)curNr - 1)) >> 1;
		return;
	}

	for (int i = l + 1; i <= primes[0] && (long long)P * primes[i] <= MAX; i++)
		back(k + 1, K, P * primes[i], i);
}

int main()
{
	freopen("pairs.in", "rt", stdin);
	freopen("pairs.out", "wt", stdout);

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", x + i);
		count[ x[i] ]++;
		if (x[i] > MAX)
			MAX = x[i];
	}

	for (int i = 3; i * i <= MAX; i += 2)
	{
		if (p[i])
			continue;

		for (int j = i * i; j <= MAX; j += i)
			p[j] = 1;
	}
	primes[ primes[0] = 1 ] = 2;
	for (int i = 3; i <= MAX; i += 2)
		if (!p[i])
			primes[ ++primes[0] ] = i;

	prod[0] = 1;
	for (int i = 1; i <= 8; i++)
		prod[i] = prod[i - 1] * primes[i];

	NR = ((long long)N * ((long long)N - 1)) >> 1;
	for (int k = 1; k <= 8; k++)
		back(0, k, 1, 0);

	printf("%lld\n", NR);

	return 0;
}