/* Generam toate numerele prime relevante pentru formarea celui mai mare numar din sir (am ales radical din 10 ^ 6 adica 1000)
   pentru fiecare posibil divizor (adica fiecare numar de la 2 la MAX) verificam din cate numere din sir face parte cel putin o data
   cautam prin numerele de la 2 la MAX numerele care se formeaza din factori primi care apar  o singura data si numaram acei factori
   daca numarul de factori primi este impar, se aduna la solutie, daca e par, se scade (principiul includerii si excluderii)
*/
#include <stdio.h>
#include <stdlib.h>

using namespace std;

bool in_v[1000001];
int p[1001];

void genereaza_nr_prime( int &nr_prime) {
    nr_prime = 0;
    bool ciur[1001] = {0};
    for (int i = 2; i <= 1000; i++) {
        if (ciur[i] == false) {
            p[nr_prime] = i;
            nr_prime++;
            for (int j = i * i; j <= 1000; j += i)
                ciur[j] = true;
        }
    }
}

int *verifica_factori_in_n(int *p, int nr_p, int *v, int n, int MAX) {
    int *x = (int*) calloc(MAX + 1, sizeof(int)), nr;
    for (int i = 2; i <= MAX; i++) {
        nr = i;
        for (int j = 1; nr <= MAX; nr += i) // cautam prin toti multiplii numarului prim
            if (in_v[nr])
                x[i]++;
    }
    return x;
}

int descompune(int nr, int nr_p) {
    int factori_distincti = 0;
    for (int i = 0; i < nr_p && nr > 1; i++)
        if (nr % p[i] == 0)
            if ((nr / p[i]) % p[i] == 0) // daca se imparte de mai mult de o data nu il vom folosi in calcul, deci returnam -1
                return -1;
            else {
                nr = nr / p[i];
                factori_distincti++;
            }
    return factori_distincti;
}

int main() {
	freopen("pairs.in", "r", stdin);
	freopen("pairs.out", "w", stdout);
	int n, MAX, v[100000];
	int *p, nr_p;
	int *x, nr_fact;
	long long sol = 0;
	scanf("%d %d", &n, &v[0]);
	MAX = v[0];
	in_v[v[0]] = true;
    for (int i = 1; i < n; i++) {
        scanf("%d", &v[i]);
        in_v[v[i]] = true;
        if (v[i] > MAX)
            MAX = v[i];
    }
    genereaza_nr_prime(nr_p);
    x = verifica_factori_in_n(p, nr_p, v, n, MAX);
    for (int i = 2; i <= MAX; i++) {
        nr_fact = descompune(i, nr_p);
        if (nr_fact > 0) {
            if (nr_fact % 2 == 0)
                sol -= (x[i] * (x[i] - 1) / 2);
            else
                sol += (x[i] * (x[i] - 1) / 2);
        }
    }
    sol = (long long int) n * (n - 1) / 2 - sol;
    printf("%lld\n", sol);
	return 0;
}