#include <bits/stdc++.h>

using namespace std;
ifstream fin("pairs.in");
ofstream fout("pairs.out");
typedef long long ll;
const ll DIM = 1e6;
int ciur1[DIM + 3]; ///ciur1[x] = cati factori primi dif are x
bool ciur2[DIM + 3]; ///ciur2[x] = daca are vreun factor prim la o putere >= 2
int frq[DIM + 3]; ///frq[x] = nr de valori divizibile cu x din vector
bool ap[DIM + 3];
int n;

inline void prelucru() {
    for(int i=2; i<=DIM; i++) {
        if(ciur1[i] == 0) { //prim
            for(int j=i; j<=DIM; j+=i) ciur1[j]++;
            if(i <= DIM / i) { //<=> i * i <= DIM
                for(ll j=i*i; j<=DIM; j+=i*i) ciur2[j] = 1;
            }
        }
    }
    for(int i=2; i<=DIM; i++)
        if(ciur2[i] == 0)
            for(int j=i; j<=DIM; j+=i) frq[i] += ap[j];
}

int main()
{
    fin >> n;
    for(int i=1; i<=n; i++) {
        int x; fin >> x;
        ap[x] = 1;
    }
    prelucru();
    ll rez = n * (n - 1) / 2; ///presupun toate perechile bune si scad/adun perechile div cu un produs de prime
    ///daca scad toate perechile div cu 2 si div cu 3 => tre sa readun perechile div cu 6
    for(int i=2; i<=DIM; i++) {
        if(ciur2[i] == 0) {
            int cnt = frq[i] * (frq[i] - 1) / 2; ///cate perechi am de elem div cu i
            if(ciur1[i] % 2 == 1) rez -= cnt;
            else rez += cnt;
        }
    }
    fout << rez;

    return 0;
}