Finding triples that satisfy given constraints in $O (n \log n) $ time
Let us shift all of your indices by $1$. The condition on the indices then becomes $j^2 = ik$. The number of factorizations of $j^2$ into $i \cdot k$ is at most $d(j)^2$, where $d(j)$ is the number of divisors of $j$.  Therefore the total number of potential triples $(i,j,k)$ is at most
$$
\sum_{j=1}^n d(j)^2 = O(n\log^3 n).
$$
(For the estimate, see this question on Mathoverflow.) Note that the actual number of triples can also be bounded by $\sum_{j=1}^n d(j^2)$, which could be smaller (and it could be yet smaller even than this sum).

This means, at the very least, that if you know $n$ in advance, then you can make a list of $\tilde{O}(n)$ triples, and solve the problem in time $\tilde{O}(n)$. Using a sieve of Eratosthenes, you can likely also calculate the triples in $\tilde{O}(n)$; it might be worthwhile to store all primes at most $500,000$ ahead of time.