【pythonでABC149を解説】C - Next Prime

問題概要

問題ページ

問題文

$X$ 以上の素数のうち、最小のものを求めよ。

注記

素数とは、$2$ 以上の整数であって、$1$ と自分自身を除くどの正の整数でも割り切れないようなもののことです。

例えば、$2, 3, 5$ は素数ですが、$4, 6$ は素数ではありません。

制約

• $2 \le X \le 10^5$
• 入力はすべて整数

問題の考察

$X$ 以上の素数のうち、最小のものを求める問題で素数の定義も注記で書いてある。

素数の定義通りにコーディングすると次のようになる。

この解き方でも$X$が小さい問題であれば特に問題にならないが、$X$が大きくなるにつれて計算量が増大する。

単純に、$100,000$の素数判定に係る時間は$10$の判定時間の$10,000$倍もかかる。

実際にコードを書いて見れば分かるが、この問題の制約ではTLEしてしまうので計算量の削減が必要になる。

実はこの判定のための計算量は次のように減らすことができる。

詳しくはこちらの解説を参照して下さい。

たびすけ

他にも「エラトステネスの篩」で素数リストを求める方法もあります。
下の「参考」でコードも掲載してるので確認してみてね。

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    x = int(input().rstrip('\n'))
    for i in range(x, 10 ** 10 + 1):
        is_prime = True
        for j in range(2, int(i ** 0.5 + 1)):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            print(i)
            exit()


if __name__ == '__main__':
    solve()

参考

気になったので素数の出現頻度がどの程度なのか確認してみた。

エラトステネスの篩で素数の最大間隔を求めてみる

エラトステネスの篩で$100,000$までの素数リストを作成し、各素数の出現間隔の最大を求めるめてみました。

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7

    prime_list = [True] * (10 ** 5 + 1)
    prime_list[0] = False
    prime_list[1] = False
    res = []
    for i in range(2, 10 ** 5 + 1):
        if prime_list[i]:
            res.append(i)
            for j in range(i, 10 ** 5 + 1, i):
                prime_list[j] = False
    max_diff = 0
    for i in range(1, len(res)):
        max_diff = max(max_diff, res[i] - res[i-1])
    print(max_diff)


if __name__ == '__main__':
    solve()

出力結果

72

ということで$100,000$までの各素数の出現間隔は最大でも100未満だと分かりました。

たびすけ

気になったことを実際にコーディングして確かめてみることは重要です！
素数の分布は数学の世界でも重要な関心事となっていますね！