using namespace std;

#include <cstdio>
#include <vector>
#include <bitset>

#define II inline
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "pairs.in"
#define OUT "pairs.out"
#define VAL_MAX 1<<20

typedef vector<int> VI;int K(-1),N;bitset<VAL_MAX> V,P;VI A(VAL_MAX),C(VAL_MAX);char buffer[VAL_MAX];II void read(int &aux){aux=0;for(;buffer[K]>'9'||buffer[K]<'0';++K);for(;buffer[K]<='9'&&buffer[K]>='0';++K)aux=aux*10+buffer[K]-'0';}II void ciur(){for(int i=2;i<VAL_MAX;++i){if(C[i])continue;for(int j=i;j<VAL_MAX;j+=i)if(P[j] == false)++C[j];if(i>1000)continue;for(int j=i*i;j<VAL_MAX;j+=i*i)P[j]=true;}for(int i=2;i<VAL_MAX;++i){if(P[i] == true)continue;for(int j=i;j<VAL_MAX;j+=i)if(V[j]==true)++A[i];}}II void scan(){int x;freopen(IN, "r",stdin);fread(buffer,1,VAL_MAX,stdin);fclose(stdin);freopen(OUT,"w",stdout);read(N);FOR(i,1,N)read(x),V[x]=true;}II ll solve(){ll rez(((ll)N*((ll)N-1))>>1);FOR(i,2,VAL_MAX){if(A[i]<2)continue;if(C[i]&1){rez-=(ll)((ll)A[i]*(ll)(A[i]-1)) / (ll)2;continue;}rez+=(ll)((ll)A[i]*(ll)(A[i]-1)) / (ll)2;}return rez;}int main(){scan();ciur();printf("%lld\n",solve());return 0;}