#include<cstdio>
#include<cmath>
long a[100000],b[100000],v[100000],n,i,max,j,m,nr,c[100000];
int main(){
	freopen("pairs.in","r",stdin);
	freopen("pairs.out","w",stdout);
	scanf("%ld",&n);max=0;
	for(i=0;i<n;i++){
		scanf("%ld",&a[i]);
		if(a[i]>max)max=a[i];
	}
	for(i=1;((i*i) << 1)+(i << 1)<=max;i++)
		if((v[i >> 3] & (1 << (i & 7)))==0){   
			for (j=((i * i) << 1)+(i << 1);(j << 1)+1<=max;j+=(i << 1)+1)
				v[j >> 3]|=(1 << (j & 7));   
		}   
    m=1;b[0]=2;
    for (i=1;2*i+1<=max;i++)     
       if((v[i >> 3] & (1 << (i & 7))) == 0)b[m++]=2*i+1;
	//for(i=0;i<m;i++)
		//printf("%ld ",m);
	for(i=0;i<n;i++)
		for(j=0;j<m && a[i]!=0;j++)
			if(a[i]%b[j]==0){
				c[j]++;
				while(a[i]%b[j]==0)
					a[i]/=b[j];
			}
	nr=0;
	for(i=0;i<m;i++)
		nr+=c[i]*(c[i]-1)/2;
	nr=(n*(n-1))/2-nr;
	printf("%ld\n",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
	}