Existence of a Repeating Divisor

Question

I have $n$ integers $a_1, a_2, a_3, .., a_n$ let $X = a_1*a_2*a_3*...*a_n$. I want to know a single integer $F$ such that $F^2$ divides $X$. It is told that there will be atleast one such $X$ and there can be many possible $F$'s, But i only need one. One easy solution is to prime factorize all the numbers and see if any divisor appears more than once, but since $a_i$ can be upto 10^18 it is not possible to factorize all the numbers. Is there any faster solution?

Answer 1

Use the Euclidean algorithm on all $\frac{n(n-1)}{2}$ pairs of $a_i$ and $a_j$. If you get a GCD that is $F > 1$, then that is your answer. This is because $F \mid a_i$ and $F \mid a_j$, so when you multiply them together, you get $F^2 \mid (a_ia_j)$, so $F^2 \mid X$.

Euclidean algorithm runs in $O(\log a_i+\log a_j)$, so since $a_i \leq 10^{18}$, it should be negligible. Thus, the algorithm will run in $O(n^2(\log a_i+\log a_j))=O(n^2)$.

However, unfortunately, we also need to check that all of the $a_i$ are square-free. According to this MathOverflow thread, this problem is in NP and co-NP, so I don't think there's a much better algorithm of doing this then finding all of the prime divisors of $a_i$ and $a_j$. Maybe Pollar's rho algorithm can help here?