ACPC2012Day2OL D.Numbers

問題

nが与えられるので、n個の連続した正の整数を求める。
ただし、その正の整数すべてについて、合成数でなければならない。

1<=n<=1500

考え方

nが大きい。
合成数の連続というのは、2つの連続する素数の差(prime gaps)が1500以上になるところが答えになる。

調べてみると、そのような素数は巨大で、だいたい23桁ぐらいになってしまう。
しかし、巨大数の素因数分解はポラードローで求められるので、上記の23桁ほどの素数の次の数をスタートとして、1500個分素因数分解し、その数の一つをあらかじめ求めておく。(C++だと64bitに収まってないので、Javaの多倍長を使った...)
あとは、nに対して、上記のスタートの数からn個を表示すればよい。