#include<stdio.h>

int n, v[1000005], fr[1000005], ciur[1000005];

int main()
{
    FILE *f = fopen("pairs.in", "r+");
    FILE *g = fopen("pairs.out", "w+");

    int rez = 0, t = 0, maxi = 0;

    fscanf(f, "%d", &n);

    for(int i = 1; i <= n; i++)
    {
        fscanf(f, "%d", &v[i]);
        if(v[i] > maxi)
            maxi = v[i];
        ciur[v[i]] = 1;
    }
    for(int i = 2; i < maxi; i++)
    {
        if(fr[i] == 0)
        {
            for(int j = i; j <= maxi; j = j + i)
                fr[j]++;
        }
    }
    for(int i = 2; i * i <= maxi; i++)
    {
        for(int j = i * i; j <= maxi; j = j + i * i)
        //frecventa fiecarui patrat al unui nr prim este initializata cu -1 pentru a putea fi exclus la parcurgere
            fr[j] = -1;
    }
    for(int i = 2; i <= maxi; i++)
    {
        //daca nu este patratul unui nr prim
        if(fr[i] != -1)
        {
            int nr = 0;
            for(int j = i; j <= maxi; j = j+ i)
            //daca ma aflu pe un numar citit din fisier, cresc nr
                {if(ciur[j] == 1)
                nr++;}
             t = nr * (nr - 1) / 2;
            //daca frecventa este nr par, inseamna ca numarul pe acre ne aflam nu este prim, ci un multiplu al unui nr prim
            if(fr[i] % 2 == 0)
            //scad din rezultatul final numarul de perechi numarate la pasul curent
                rez = rez - t;
                //altfel adaug la rezultatul final numarul de perechi de la pasul curent
            else rez = rez + t;
        }
    }
    //t = n * (n - 1) / 2;
    //calculez nr de perechi viabile
   // rez = rez - t;
    fprintf(g, "%d", rez);

}