けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 149 C - Next Prime (300 点)

C 問題で整数系のアルゴリズムを確認する問題を出すの良さそうやね。

問題へのリンク

問題概要

2 以上の整数  X が与えられる。 X 以上の最小の素数を求めよ。

制約

  •  2 \le X \le 10^{5}

素数判定

整数  N素数かどうかを判定するのは、整数論アルゴリズムで最初くらいに学ぶものですね。まず素数の定義を確認する。


正の整数  N素数であるとは、 N 1 N のみで割り切れることである


素数かどうかを判定する方法は、素数の定義に素直に従えば OK。

  •  N 2, 3, \dots, N-1 と順に割っていって
    • どこかで割れてしまったら合成数
    • ずっと割り切れなかったら素数

という方法。たとえば  N = 7 は、2, 3, 4, 5, 6 で割り切れないので素数 N = 35 は 5 や 7 で割り切れてしまうので合成数

しかしこのままでは  N-2 通りを調べる必要があるので  O(N) の計算量を要してしまう。

素数判定の効率化

実は、たとえば 97 が素数であることを確かめるのに、96 まで試し割りする必要はない。 9 まで試せば十分なのだ。

なぜなら、

  • 97 ÷ 2 = 48.5
  • 97 ÷ 3 = 32.333...
  • 97 ÷ 4 = 24.25
  • 97 ÷ 5 = 19.4
  • 97 ÷ 6 = 16.166...
  • 97 ÷ 7 = 13.857...
  • 97 ÷ 8 = 12.125
  • 97 ÷ 9 = 10.777...
  • 97 ÷ 10 = 9.7

となっていきますが、

  • 97 ÷ 9 の時点では、その計算の答えの 10.777... が、割る数の 9 よりも大きいが、
  • 97 ÷ 10 の時点で、その計算の答えの 9.7 が、割る数の 10 よりも小さい

という逆転が起こっているのです!!!!!
ここから導きだされる結論は、


もし仮に、97 が 10 以上の整数  x で割り切れるのならば、

 97 = x \times y

という風にしたときに、 y x よりも小さい。つまり、97 は  x よりも先に  y で割り切れているはずなのだ!!!


というわけで、97 が 10 以上の整数で割り切れるようだったら、それ以前に割り切れているはずなので、9 まで試せばよい、というわけだ。

一般には

今回は 97 について考えたが、一般の整数  N についても似たことがいえる。具体的には


 N i = 2, 3, \dots, で試し割りしていったときに、

 i \times i \gt N となったら打ち切って良い


ということがいえる。つまり  i \le \sqrt{N} の範囲を調べることになるので、計算量は  O(\sqrt{N}) となる。

以上をまとめると、素数判定は以下のように書ける ( N = 0, 1 の場合は例外処理)。

bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}

今回の問題に戻って

今回の問題は、 X, X+1, X+2, \dots と順に素数かどうかを調べていって、素数だとわかったらそれをリターンすれば OK。

ちなみに、 X をどこまでインクリメントすればよいのだろう...という不安が当然頭をよぎるのだけど、100003 が素数なので心配ない。 X \le 100000 なので、最悪時でも 100003 で止まる。

#include <iostream>
using namespace std;

bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}

int main() {
    long long X;
    cin >> X;
    long long res = X;
    while (!is_prime(res)) ++res;
    cout << res << endl;
}