#include <stdio.h>
#include <fstream>
#include <vector>
using namespace std;

#define in "pairs.in"
#define out "pairs.out"
#define dim 100001

int N, M, Q=0;
int maxim = 0;
int A[dim];
int Poz[1000002], P[78499];
bool ok[1000002];
vector<int> L[78499];

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    // numere prime
    
    memset(ok,0,sizeof(ok));
    for ( int i = 2; i*i <= 1000000; i++ )
    {
        int j = 2;
        while ( i*j <= 1000000 ) ok[i*j] = 1, j++;
    }
    
    int t=0;
    
    for ( int i = 2; i <= 1000000; i++ )
        if ( ok[i] == 0 ) Poz[i] = t, P[t] = i, t+=1;
    //
    
    scanf("%d", &N);
    for ( int i = 1; i <= N; i++ ) scanf("%d", &A[i]);
    
    for ( int i = 1; i <= N; i++ )
    {
        M = A[i];
        for ( int j = 0; P[j]*P[j] <= M; j++ )
        {
            if ( M % P[j] == 0 )
            {
                 while ( M % P[j] == 0 && M >= P[j] ) M /= P[j];
                 L[j].push_back(i);
            }
        }
        
        if ( M > 1 ) L[Poz[M]].push_back(i);
    }
    
    unsigned long long Total = (N*(N-1))/2;
    unsigned long long aux1;
    
    for ( int i = 0; i < 78498; i++ )
    {
        if ( L[i].size() >= 2 )
        {
             aux1 = ( L[i].size() ) * ( L[i].size()-1 );
             aux1 /= 2;
             
             Total -= aux1;
        }
    }

    printf("%llu", Total);    
}