#include <bits/stdc++.h>

using namespace std;

    ifstream fin("pairs.in");
    ofstream fout("pairs.out");
const int valMAX = 1e6+6;
int fr[valMAX], n;

///citesc si marchez numerele din vector
void partOne(){
    int i, val;
    fin >> n;
    for(i = 1; i <= n; ++i){
        fin >> val;
        ++fr[val];
    }
}

bitset <valMAX> a;
int prime[100004], nrPrime;
void ciur(){
    a[1] = 1;
    int i, j;
    for(i = 4; i < valMAX; i += 2)
        a[i] = 1;

    for(i = 3; i * i < valMAX; ++i)
        if(!a[i])
            for(j = i*i; j < valMAX; j += i)
                a[j] = 1;

    prime[++nrPrime] = 2;
    for(i = 3; i < valMAX; i += 2)
        if(!a[i])
        prime[++nrPrime] = i;

   /* for(i = 1; i <= nrPrime; ++i)
        fout << prime[i] << '\n';*/
}


///parcurg vectorul de marcat
///atunci cand gasesc un numar nou il descompun in factori primi
///pentru fiecare factor cresc numarul de multiplii cu 1
///apoi folosesc principiul includerii si excluderii pentru a vedea cu cate numere din sir
///are numarul actual cmmdc = 1

int mult[valMAX];
int fac[10], nrFac, cate;
void desc(int val){
    nrFac = 0;
    int d;


    for(d = 1; d * d < val; ++d){
        if(val % d == 0){
            mult[d] += fr[val], mult[val/d] += fr[val];

            if(!a[d])
                fac[++nrFac] = d;

            if(!a[val/d])
                fac[++nrFac] = val/d;
        }

    }

    if(d * d == val){
        mult[d] += fr[val];

        if(!a[d])
            fac[++nrFac] = d;
    }

}


///am uitat bckt =))))
long long includeExclude(){
    long long sol = 0;
    if(nrFac >= 1){
        int a1;
        for(a1 = 1; a1 <= nrFac; ++a1)
            sol -= mult[fac[a1]];
    }

    if(nrFac >= 2){
        int a1, a2, prod;
        for(a1 = 1; a1 <= nrFac - 1; ++a1){

            for(a2 = a1 + 1; a2 <= nrFac; ++a2)
                prod = fac[a1] * fac[a2], sol += mult[prod];
        }
    }

    if(nrFac >= 3){
        int a1, a2, a3, prod;
        for(a1 = 1; a1 <= nrFac - 2; ++a1){

            for(a2 = a1 + 1; a2 <= nrFac - 1; ++a2){

                for(a3 = a2 + 1; a3 <= nrFac; ++a3)
                    prod = fac[a1] * fac[a2] * fac[a3], sol -= mult[prod];
            }

        }
    }

    if(nrFac >= 4){
        int a1, a2, a3, a4, prod;
        for(a1 = 1; a1 <= nrFac - 3; ++a1){

            for(a2 = a1 + 1; a2 <= nrFac - 2; ++a2){

                for(a3 = a2 + 1; a3 <= nrFac - 1; ++a3){

                    for(a4 = a3 + 1; a4 <= nrFac; ++a4)
                        prod = fac[a1] * fac[a2] * fac[a3] * fac[a4], sol += mult[prod];
                }

            }

        }
    }

    if(nrFac >= 5){
        int a1, a2, a3, a4, a5, prod;
        for(a1 = 1; a1 <= nrFac - 4; ++a1){

            for(a2 = a1 + 1; a2 <= nrFac - 3; ++a2){

                for(a3 = a2 + 1; a3 <= nrFac - 2; ++a3){

                    for(a4 = a3 + 1; a4 <= nrFac - 1; ++a4){

                        for(a5 = a4 + 1; a5 <= nrFac; ++a5)
                            prod = fac[a1] * fac[a2] * fac[a3] * fac[a4] * fac[a5], sol -= mult[prod];
                    }

                }

            }

        }
    }

    if(nrFac >= 6){
        int a1, a2, a3, a4, a5, a6, prod;
        for(a1 = 1; a1 <= nrFac - 5; ++a1){

            for(a2 = a1 + 1; a2 <= nrFac - 4; ++a2){

                for(a3 = a2 + 1; a3 <= nrFac - 3; ++a3){

                    for(a4 = a3 + 1; a4 <= nrFac - 2; ++a4){

                        for(a5 = a4 + 1; a5 <= nrFac - 1; ++a5){

                            for(a6 = a5 + 1; a6 <= nrFac; ++a6)
                                prod = fac[a1] * fac[a2] * fac[a3] * fac[a4] * fac[a5] * fac[a6], sol += mult[prod];
                        }

                    }

                }

            }

        }
    }

    if(nrFac >= 7){
        int a1, a2, a3, a4, a5, a6, a7, prod;
        for(a1 = 1; a1 <= nrFac - 6; ++a1){

            for(a2 = a1 + 1; a2 <= nrFac - 5; ++a2){

                for(a3 = a2 + 1; a3 <= nrFac - 4; ++a3){

                    for(a4 = a3 + 1; a4 <= nrFac - 3; ++a4){

                        for(a5 = a4 + 1; a5 <= nrFac - 2; ++a5){

                            for(a6 = a5 + 1; a6 <= nrFac - 1; ++a6){

                                for(a7 = a6 + 1; a7 <= nrFac; ++a7)
                                    prod = fac[a1] * fac[a2] * fac[a3] * fac[a4] * fac[a5] * fac[a6] * fac[a7], sol -= mult[prod];
                            }

                        }

                    }

                }

            }

        }
    }

    if(nrFac >= 8){
        int a1, a2, a3, a4, a5, a6, a7, a8, prod;
        for(a1 = 1; a1 <= nrFac - 7; ++a1){

            for(a2 = a1 + 1; a2 <= nrFac - 6; ++a2){

                for(a3 = a2 + 1; a3 <= nrFac - 5; ++a3){

                    for(a4 = a3 + 1; a4 <= nrFac - 4; ++a4){

                        for(a5 = a4 + 1; a5 <= nrFac - 3; ++a5){

                            for(a6 = a5 + 1; a6 <= nrFac - 2; ++a6){

                                for(a7 = a6 + 1; a7 <= nrFac - 1; ++a7){

                                    for(a8 = a7 + 1; a8 <= nrFac; ++a8)
                                        prod = fac[a1] * fac[a2] * fac[a3] * fac[a4] * fac[a5] * fac[a6] * fac[a7] * fac[a8], sol += mult[prod];
                                }

                            }

                        }

                    }

                }

            }

        }
    }

    return sol;
}

void partTwo(){
    int i, j, nCurent = 0;
    long long sol = 0;

    for(i = 2; i < valMAX; ++i){
        if(fr[i] == 0)
            continue;

        ///marchez factorii primi
        desc(i);

        /*fout << i << ' ';
        for(j = 1; j <= nrFac; ++j)
            fout << fac[j] << ' ';
        fout << '\n';*/
        ///din cele n numere scad numerele care nu sunt bune

        nCurent += fr[i];
        sol += nCurent;
        sol += includeExclude();
    }

    fout << sol;
}
int main()
{


    ciur();
    partOne();
    partTwo();



    return 0;
}