#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

const int MAXV = 1e6;

bool ciur[1 + MAXV], f[1 + MAXV], in[1 + MAXV];
int cnt[1 + MAXV];

int main() {
  int n, x;

  fin >> n;
  for ( int i = 1; i <= n; ++i ) {
	fin >> x;
	in[x] = true;
  }
  for ( int d = 2; d <= MAXV; ++d ) {
	if ( ciur[d] == 0 ) {
	  for ( int i = d + d; i <= MAXV; i += d ) {
        ciur[i] = 1;
	    ++cnt[i];
	    f[i] |= (i % (d * d) == 0);
	  }
	}
  }
  ll res = 0;
  for ( int d = 2; d <= MAXV; ++d ) {
	if ( !f[d] ) {
		cout << d << "\n";
	  int k = 0;
	  for ( int i = d; i <= MAXV; i += d ) {
		k += in[i];
	  }
	  res += (ll)k * (k - 1) / 2 * (cnt[d] % 2 ? -1 : 1);
	}
  }
  fout << (ll)n * (n - 1) / 2 - res;
  fin.close();
  fout.close();
  return 0;
}