Given an integer $a \ge 2$, we want to find a pair $(d_1, d_2)$ that satisfies $gcd(d_1+d_2, a)=1$. However, $d_1 \ge 2$ and $d_2 \ge 2$. Repeat this $n$ times.
First, perform prime factorization as $a = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdots {p_m}^{k_m}$. If $m = 1$ or $a$ is prime, the answer is $(-1, -1)$. If $m \ge 2$, the answer is $(p_1, p_2 \cdot p_3 \cdots p_m)$.
Let’s look at why this is the correct answer. It suffices to show that “$d_1 + d_2$ is not divisible by any prime factor $p_i$”. First, consider whether “$d1 + d2$ is not divisible by $p1$” is correct. From $d1 \equiv 0, d2 \not \equiv 0 (mod \ p_1)$, we get $d1 + d2 \not \equiv 0 (mod \ p_1)$. Next, consider whether “$d1 + d2$ is not divisible by $p_i (2 \le i \le m)$” is correct. From $d1 \not \equiv 0, d2 \equiv 0 (mod \ p_i)$, we get $d1 + d2 \not \equiv 0 (mod \ p_i)$.
Since naively performing prime factorization each time $a$ is given in $n$ loops won’t be fast enough,
it’s good to pre-compute the minimum prime factor minPrime[x] that value $x$ has, using the Sieve of Eratosthenes approach.