【ABC149 C】「Next Prime」を解く【Python3】

abc149c

コンテスト一覧へ

 

X以上の素数のうち最小のものを求める問題です。

Xから順番に数を増やしていき、素数かどうかを調べるとうまくいきます。

提出
import math
x = int(input())

for i in range(x, 100004):
    flag = True
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            flag = False
            break
    if flag:
        print(i)
        exit(0)

Xは「100000」までという制約があります。

100000 以上の最小の素数は、入力例3から「100003」ということがわかります。

それ以上の素数は考えなくていいことから、100003までの数字を順番に調べることにします。

調べている数字「i」が2以上の数字で割り切れるかどうかを判定し、割り切れる場合は「flag = False」と変え、最後まで「flag = True」だった数字「i」が答えになります。

割る方の数字は、「i」の平方根(小数点以下切り捨て)までで大丈夫です。

for j in range(2, math.floor(math.sqrt(i))+1):

【ABC149】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。