#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
#define N 1001000
int v[N],it,i,n,x,MAX,cnt,d[N],numar_prime[N],j;
long long ans,curr;
int main()
{
    ifstream fin ("pairs.in");
    fin >> n;
    ans = 1LL * n * (n - 1) / 2;
    MAX = 0;
    for (i = 0; i < n; ++i){
        fin >> x;
        v[x] = 1;
        MAX = max(MAX,x);
    }
    for (i = 2; i < MAX + 1; ++i){
        if(!numar_prime[i]){
            for (j = i; j < MAX + 1; j += i)
                ++numar_prime[j];
        }
    }
    for (i = 2; i * i < MAX + 1; ++i){
        for (j = i * i; j < MAX + 1; j += i * i)
            numar_prime[j] = 0;
    }
    for (i = 0; i < MAX; ++i)
        d[i] = 0;
    for (it = 2; it < MAX; ++it){
        cnt = numar_prime[it];
        if (cnt){
            for (i = 0; i < MAX / it + 1; ++i)
                d[it] += v[i * it];
            curr = 1LL * d[it] * (d[it] - 1) / 2;
            if (cnt & 1)
                ans -= curr;
            else
                ans += curr;
        }
    }
    ofstream fout ("pairs.out");
    fout << ans;
    return 0;
}