#include <cstdio>

const int MAX_L = 1000010;

int n, max;
int f[MAX_L], c[MAX_L], a[MAX_L];

int main()
{
	int i, j, x;
	freopen("pairs.in", "r", stdin);
	freopen("pairs.out", "w", stdout);
	
	scanf("%d", &n);
	
	long long rez = (long long)n * (n - 1) / 2;
	
	for (i = 1; i <= n; scanf("%d", &x), f[x] = 1, max = (x > max) ? x : max, ++i);
	
	for (i = 1; i <= max; a[i] = 1, ++i);
	
	for (i = 2; i <= max; ++i)
		if (!c[i])
			for (j = i; j <= max; ++c[j], a[j] *= i, j += i);
		
	for (i = 2, x = 0; i <= max; rez += (long long)((a[i] == i) ? 1 : 0) * ((c[i] & 1) ? -1 : 1) * x * (x - 1) / 2, ++i, x = 0)
		if (a[i] == i)
			for (j = i; j <= max; x += f[j], j += i);
		
	printf("%lld\n", rez);
}