整数$a \ge 2$が与えられるので、$gcd(d_1+d_2,a)=1$を満たすような組$(d_1,d_2)$を求めたい。 ただし、$d_1 \ge 2$かつ$d_2 \ge 2$。 これを$n$個回繰り返す。
まず $a = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdots {p_m}^{k_m}$ のように素因数分解を行う。 もし $m = 1$あるいは$a$が素数の場合には、答えは$(-1,-1)$。 $m \ge 2$の場合には、$(p_1, p_2 \cdot p_3 \cdots p_m)$が答えとなる。
なぜこれが答えでよいのか見ていく。 「$d_1 + d_2$がいかなる素因数$p_i$に対しても割り切れないこと」が言えればよい。 まず、「$d1 + d2$ が $p1$ で割り切れない」ことが正しいのか考えてみる。 $d1 \equiv 0, d2 \not \equiv 0 (mod \ p_1) $ より、$d1 + d2 \not \equiv 0 (mod \ p_1)$ となる。 続いて、「$d1 + d2$ は $p_i (2 \le i \le m)$ で割り切れない」ことが正しいのか考えてみる。 $d1 \not \equiv 0, d2 \equiv 0 (mod \ p_i) $ より、$d1 + d2 \not \equiv 0 (mod \ p_i)$ となる。
$n$回のループで$a$が与えられるたびにナイーブに素因数分解を行うと間に合わないので、
あらかじめ値$x$が持つ最小の素因数 minPrime[x] を、エラトステネスの篩の要領で求めておくとよい。