#include <fstream>
#include <vector>
//#include <iostream>
//#include <random>
//#include <cstring>

using namespace std;

ifstream fin ("pairs.in");
ofstream fout ("pairs.out");

int n, nr;
int a[100005], v[1000005], NR[1000005], b[100005];
bool m[1000005];

vector <int> c[100005];

int cmmdc(int x, int y)	 {
	int r = x % y;
	while (r)	 {
		x = y;
		y = r;
		r = x % y;
	}
	return y;
}

int brut()	{
	int ans = 0;
	for (int i = 1; i <= n; ++i)	{
		for (int j = i + 1; j <= n; ++j)	{
			if (a[i] != a[j] && cmmdc(a[i], a[j]) == 1)
				++ans;
		}
	}
	return ans;
}

long long pinex(int x)	{
	long long ans = 0;
	int lim = 1 << (c[x].size());
	for (int j = 1; j < lim; ++j)	 {
		int div = 1, nr1 = 0;
		for (int s = j, k = 0; s; s >>= 1, ++k)	{
			if (s & 1)
				div *= c[x][k], ++nr1;
		}
		--NR[div];
		if (nr1 & 1)
			ans += NR[div];
		else
			ans -= NR[div];
	}
	return n - x - ans;
}

long long solve()	{

//	nr = 0;
//	memset(m, 0, sizeof(m));
//	memset(v, 0, sizeof(v));
//	memset(NR, 0, sizeof(NR));
////	memset(c, 0, sizeof(c));
//	for (int i = 1; i <= 100000; ++i)
//		c[i].clear();


	for (int i = 4; i <= 1000000; i += 2)	{
		m[i] = true;
	}
	for (int i = 3; i * i <= 1000000; i += 2)	 {
		if (!m[i])	{
			for (int j = i * i; j <= 1000000; j += i)
				m[j] = true;
		}
	}
	for (int i = 2; i <= 1000000; ++i)
		if (!m[i])
			v[++nr] = i;
	for (int i = 1; i <= n; ++i)
		b[i] = a[i];
	for (int i = 1; i <= n; ++i)	{
		for (int j = 1; j <= nr && b[i] > 1; ++j)	 {
			if (b[i] % v[j] == 0)	{
				c[i].push_back(v[j]);
				while (b[i] % v[j] == 0)
					b[i] /= v[j];
			}
		}
		int lim = 1 << (c[i].size());
		for (int j = 1; j < lim; ++j)	 {
			int div = 1;
			for (int s = j, k = 0; s; s >>= 1, ++k)	{
				if (s & 1)
					div *= c[i][k];
			}
			++NR[div];
		}
	}
	long long ans = 0;
	for (int i = 1; i <= n; ++i)	{
		ans += pinex(i);
	}
	return ans;
}

//int random(int from, int to){
//    return rand() % (to - from + 1) + from;
//}

int main()	{
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> a[i];
//	srand(time(0));
//	do	 {
//		for (int i = 1; i <= n; ++i)	{
//			a[i] = random(2, 1000000);
//		}
//		cout << "OK\n";
//	} while (brut() == solve());
//	for (int i = 1; i <= n; ++i)
//		fout << a[i] << '\n';

	if (n <= 1000)	{
		fout << brut();
		return 0;
	}
	long long ans = 0;
	ans = solve();
	fout << ans;
	return 0;
}