2007/Contest/東京大会

Problem B : Prime Gap †

問題概要 †

連続した素数 p と p+n の間の合成数の列 p+1, p+2, ..., p+n-1 を、長さ n の "Prime Gap" と呼ぶ。 (合成数の列の長さは n-1 だが "Prime Gap" の長さは n である)

与えられた整数 (<= 1299709) を含む Prime Gap の長さを出力せよ。
与えられた整数が素数の場合は 0 を出力せよ。 (三廻部; Nov 11, 2007)

解法 †

エラトステネスの篩などを用いて素直に素数を求めておき、与えられた整数の前後の素数を探す。あとはその差を求めればよい。 (三廻部; Nov 11, 2007)

議論・その他 †

ファイルを添付する †

mikurube_B.cpp