#include <stdio.h>

#define MAX_VAL 1000000
#define MAX_P 78500
#define LIMIT 1000

#define ll long long

int N;
int freq[MAX_P];            /* de cate ori apare un numar prim in reprezentarea
                               divizorilor numerelor din fisier. */
int low[MAX_VAL + 1];       /* low[i] este cel mai mic numar prim care il divide
                               pe "i". */
int size, ptr[MAX_VAL + 1]; /* ptr[i] este pozitia in vectorul numerelor prime
                               daca "i" este numar prim. */

/** Ciurul lui Eratostene. **/
void sieve() {
  int i, j, step;

  low[2] = 2;
  ptr[2] = size++;
  for (i = 3; i < LIMIT; i += 2) {
    if (!low[i]) {
      low[i] = i;
      ptr[i] = size++;
      for (step = (i << 1), j = i * i; j <= MAX_VAL; j += step) {
        if (!low[j]) {
          low[j] = i;
        }
      }
    }
  }
  for (; i < MAX_VAL; i += 2) {
    if (!low[i]) {
      low[i] = i;
      ptr[i] = size++;
    }
  }
}

/** Obtine divizorii lui "x". **/
void getDiv(int x) {
  int curr;
  
  if (x % 2 == 0) {
    freq[0]++;
    x /= (x & -x);
  }
  while (x > 1) {
    curr = low[x];
    do {
      x /= curr;
    } while (curr == low[x]);
    freq[ptr[curr]]++;
  }
}

int main(void) {
  int i, val;
  FILE *f = fopen("pairs.in", "r");

  sieve();

  /* Citirea datelor. */
  fscanf(f, "%d", &N);
  for (i = 0; i < N; i++) {
    fscanf(f, "%d", &val);
    getDiv(val);
  }
  fclose(f);

  /* Calcularea solutiei. */
  ll int count = 0;
  for (i = 0; i < MAX_P; i++) {
    if (freq[i]) {
      count += (ll)freq[i] * (freq[i] - 1) / 2;
    }
  }
  count = ((ll)N * (N - 1) / 2) - count;

  /* Afisarea solutiei. */
  freopen("pairs.out", "w", stdout);
  fprintf(stdout, "%lld\n", count);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}