/* 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];
int x[1000001], spf[1000001];

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;
        }
    }
}

void genereaza_spf(int nr_p, int n) {
    for (int i = 1; i <= n; i++)
        spf[i] = i;
    for (int i = 0; i < nr_p; i++)
        for (int j = p[i] * p[i]; j <= n; j += p[i])
            if (spf[j] == j)
                spf[j] = p[i];
}

int verifica_factori_in_n(int nr_p, int *v, int n, int MAX) {
    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]++;
    }
}

int descompune(int nr) {
    int factori_distincti = 0, prev = -1;
    while (nr != 1) {
        if (spf[nr] == prev) // daca se imparte de mai mult de o data nu il vom folosi in calcul, deci returnam -1
            return -1;
        factori_distincti++;
        prev = spf[nr];
        nr = nr / spf[nr];
    }
    return factori_distincti;
}

int main() {
	freopen("pairs.in", "r", stdin);
	freopen("pairs.out", "w", stdout);
	int n, MAX, v[100000];
	int nr_p;
	int 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);
    genereaza_spf(nr_p, MAX);
    verifica_factori_in_n(nr_p, v, n, MAX);
    for (int i = 2; i <= MAX; i++) {
        nr_fact = descompune(i);
        if (nr_fact > 0) {
            if (nr_fact % 2 == 0)
                sol -= (1ll * x[i] * (x[i] - 1) / 2);
            else
                sol += (1ll * x[i] * (x[i] - 1) / 2);
        }
    }
    sol = (long long int) n * (n - 1) / 2 - sol;
    printf("%lld\n", sol);
	return 0;
}