NGCD - NO GCD

给定数组a[]，求多少对(i,j)，使得a[i]，a[j]互质或者gcd是质数，保证a[]只有小于50的素因子，而且不含平方因子。

You are given N(1<=N<=100000) integers. Each integer is square free(meaning it has no divisor which is a square number except 1) and all the prime factors are less than 50. You have to find out the number of pairs are there such that their gcd is 1 or a prime number. Note that (i,j) and (j,i) are different pairs if i and j are different.