#include<stdio.h>
#define N 100000
int v[N];
void ciur(){
	for(int i=2;i<N;++i)
		if(v[i]==0){
			v[i]=i;
			for(int j=i+i;j<N;j+=i)
				v[j]=i;
		}
}
int desc(int x){
	int s=0;
	while(x>1){
		x/=v[x];
		s++;
	}
	return s;
}
int main(){
	int n,c[N],i,s=0;
	freopen("pairs.in","r",stdin);
	freopen("pairs.out","w",stdout);
	scanf("%d",&n);
	s=n*(n-1)/2;
	ciur();
	for(i=0;i<n;++i)
		scanf("%d",&c[i]);
	for(i=0;i<n;++i)
		if(desc(c[i])%2)
			s-=v[c[i]]*(v[c[i]]-1)/2;
		else
			s+=v[c[i]]*(v[c[i]]-1)/2;
	printf("%d\n",s);
	fclose(stdin);
	fclose(stdout);
	return 0;
}