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

}