\(N:=10^5,M:=2\times 10^6\) としましょう。

ここで、 \(D:=\left\lfloor M^{2/3} \right \rfloor\) とします。

また、長さ \(2(N-D)\) の数列 \(V\) を、 \(D\) を超える素数を小さい順に列挙したものとします。ここで、 \(2\times 10^6 \le V_{2(N-D)}\) です。

このとき、\(A=(1,2,\ldots,D,V_1,\ldots,V_{N-D}), B=(1,2,\ldots,D,V_{N-D+1},\ldots,V_{2(N-D)})\) とすると条件を満たします。このことを示しましょう。

\(M^{1/3}\) 以上の素数を約数として含む場合

• その素数を \(p\) としたとき、数を \(pt(t \le M^{2/3})\) と表現することができます。 \(t\) は \(A,B\) どちらにも存在し、 \(p\) はどちらかに存在します。

そうでない場合

• 数を \(nm(n\le m)\) と表現することにしたとき、 \(M^{1/3} \le m/n\) ならば \(m\) が含む素因数を一つ \(n\) に移すことで \(\max(n/m,m/n)\) をより小さくできますから、 \(m/n < M^{1/3}\) である表現が可能です。このとき、 \(n,m < M^{2/3}\) ですから \(n,m\) は \(A,B\) どちらにも存在します。

実装例