#include <iostream>
#include <fstream>

using namespace std;

const int N = 1000005;
const int M = 100005;

long long i, j, maxim , n, sol, v_frecventa[N], v[M], w[N], z[N];
bool viz[N];

int main()
{
    ifstream in ("pairs.in");
    ofstream out ("pairs.out");

    maxim = 0;

    in>>n;
//    v = new long long [n];

	for(i = 1; i <= n; i++)
	{
		in >> v[i];
		viz[ v[i] ] = true;
		if (v[i] >= maxim)
            maxim = v[i];
	}

//    v_frecventa = new long long [maxim + 1];
//    z = new long long [maxim + 1];
//    w = new long long [maxim + 1];
//    viz = new bool [maxim + 1];

//	for (i = 1; i <= maxim; i++)
//		v_frecventa[i] = 0;

	for (i = 2; i <= maxim; i++)
		for (j = i; j <= maxim; j+= i)
			if(viz[j] == true)
                v_frecventa[i]++;

	for (i = 1; i <= maxim; i++)
        z[i] = 1;

	for (i = 2; i * i <= maxim; i++)
		for (j = 2; j <= maxim / i; j++)
			z[i * j] = z[i] + z[j];

	for (i = 2; i <= maxim; i++)
	{
		if(z[i] == 1 && i <= 1000)
			w[i * i] = 1;

		if(w[i] == 1)
		{
			for (j = 2; j <= maxim / i; j++)
				w[i * j] = 2;
		}
	}
	sol = n * (n - 1) / 2;

	for (i = 2; i <= maxim; i++)
	{
		if(w[i] == 0)
		{
			if(z[i] % 2 == 0)
			{
				sol = sol + v_frecventa[i] * (v_frecventa[i] - 1) / 2;
			}
			else sol = sol - v_frecventa[i] * (v_frecventa[i] - 1) / 2;
		}
	}

	out << sol;

//	delete( viz );
//	delete( v_frecventa );
//	delete( w );
//	delete( v );
//	delete( z );

	in.close();
	out.close();

	return 0;
}