Next Prime [AtCoder Beginner Contest 149 C]

https://atcoder.jp/contests/abc149/tasks/abc149_c

前提知識

• エラトステネスの篩

解説

https://atcoder.jp/contests/abc149/submissions/9263189

素数判定をするが、雑な解き方をすると、10⁶までの素数を全列挙して、X以上の最小の素数を答えればいい。
1～10⁶の素数を得るためには、エラトステネスの篩を使えばいい。
1つ1つ素数であるかを判定するのは大変だが、区間なら効率的に判定できることが知られている。
自分はライブラリ化してあるので、それを貼って10⁶までの素数を求めて、lower_boundでX以上の最小値を持ってきて答える。

int X;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X;

    auto vp = makePrimes(1000000);
    int ans = *lower_bound(all(vp), X);
    cout << ans << endl;
}