Find pairs in two arrays such that when multiplied becomes a perfect square

Question

Given two integer arrays like this:-

int[] a = { 2, 6, 10, 13, 17,18 };
int[] b = { 3, 7, 8, 9, 11, 15 };

How can I find pairs from these two arrays such that when multiplied they become perfect square?

For eg, in above arrays {2,8} & {18,8} are two pairs.

Right now my approach is brute-force, where I am looping through both arrays like this:-

int count = 0;
for (int i = 0; i < arr1.Length; i++)
{
    for (int j = 0; j < arr2.Length; j++)
    {
         var x = arr1[i] * arr2[j];
         long s = (long)Math.Sqrt(x);
         if (x == s * s)
               count += 1;                   
     }
}

How can I do this efficiently?

Answer 1

Any two numbers where the count of each prime factor in the number is even, would form a valid pair. Otherwise, any number with an odd count of one or more prime factors could only pair with another number with the exact same factors having an odd count. This means all we would need to store for each number is which of its prime factors have an odd count. This could be hashed.

a = { 2, 6, 10, 13, 17,18 }; 
b = { 3, 7, 8, 9, 11, 15 };

Hash the shorter array where the key is the combination of prime factors with odd count and the value is the corresponding list of indexes in the array:

a = {
  2: [0,5],
  2-3: [1], 
  2-5: [2], 
  13: [3],
  17: [4]
}

Traverse the second array and exactly match the prime-factor-with-odd-count-combination:

b[0] -> 3, no match
b[1] -> 7, no match
b[2] -> 2, match with a[0] and a[5] -> 2 * 8 and 18 * 8 are perfect squares
b[3] -> None, no match
b[4] -> 11, no match
b[5] -> 3-5, no match