#include <cstdio>
#include <algorithm>


long nr, i,n,j;
long A[100000];

long brut1() {
	nr = 0;
	for (i=0; i<n; ++i)
		for (j=i+1; j<n; ++j) {
			long x = A[i], y = A[j], r;
			while ( x ) { r=y%x; y=x; x=r; }
			if ( y==1 ) nr++;
		}
	return nr;
}


char p[1000020>>4];
long Prim[80000];
  
long sieve(int n) {   
	int i, j, nr = 1;   
	for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1)
		if ((p[i >> 3] & (1 << (i & 7))) == 0)
			for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1)
				p[j >> 3] |= (1 << (j & 7));
	Prim[0] = 2;
	for (i = 1; 2 * i + 1 <= n; ++i)     
		if ((p[i >> 3] & (1 << (i & 7))) == 0)
			Prim[nr++] = 2*i+1;   
	return nr;   
} 

long Nr[100000];

long brut2() {
	long k = sieve(A[n-1]);	// TODO : debug
	for (i=0; i<n; ++i) Nr[i] = i;
	for (i=0; i<k; ++i) {
		long delta = 0;
		for (j=0; j<n; ++j)
			if ( A[j] % Prim[i] == 0 ) {
				Nr[j]-=delta;
				delta++;
			}
	}

	nr = 0;
	for (i=0; i<n; ++i)
		nr += Nr[i];
	return nr;
}


int main() {
	freopen("pairs.in", "r", stdin);
	scanf("%ld", &n);
	for (i=0; i<n; ++i)
		scanf("%ld", A+i);
	fclose(stdin);

	std::sort(A, A+n);

	freopen("pairs.out", "w", stdout);
	printf("%ld\n", brut2());
	fclose(stdout);
	return 0;
}