#include <stdio.h>
#define MAX_L  1000010
int n, max;
int f[MAX_L], c[MAX_L], a[MAX_L];
int main()
{
    int i, j, x;
    freopen("pairs.in", "r", stdin);
    freopen("pairs.out", "w", stdout);

    scanf("%d", &n);

    long long rez = (long long)n * (n - 1) / 2;

    for (i = 1; i <= n;++i){
        scanf("%d", &x);
        f[x] = 1;
        max = (x > max) ? x : max ;
    }

    for (i = 1; i <= max; ++i)
        a[i] = 1;

    for (i = 2; i <= max; ++i)
        if (!c[i])
            for (j = i; j <= max; j += i){
                ++c[j];
                a[j] *= i ;
            }

    for (i = 2, x = 0; i <= max; rez += (long long)((a[i] == i) ? 1 : 0) * ((c[i] & 1) ? -1 : 1) * x * (x - 1) / 2, ++i, x = 0)
        if (a[i] == i)
            for (j = i; j <= max;j += i)
                x += f[j];

    printf("%lld\n", rez);
}