【AtCoder】ARC017解説（Python）

AtCoder Regular Contest 017の解説記事です。

ARC017 A – 素数、コンテスト、素数

問題

問題文の要約は以下の通りです。

問題の要約

\(N\) （\(17 \leq N \leq 1000000 \) ）が素数か判定せよ。

解説

2からその平方根までの数で割り切れない場合にYES、割り切れる場合にNOを出力する。

解説

mathというPythonの数学ライブラリをインポートします。このライブラリには、平方根を計算するためのmath.sqrt()関数が含まれています。

import math

整数を入力として受け取り、その値を変数Nに格納します。

# 入力
N=int(input())

2からNの平方根までの整数を順に調べます。

素数でない数（合成数）は必ず小さい因数と大きい因数のペアが存在するので、平方根まで確認すれば素数かどうかを判断できます。

# ルート N まで割り切れるか判定する
for i in range(2, int(math.sqrt(N)) + 1):

Nがiで割り切れるかどうかをチェックします。もし割り切れる場合は、Nは素数ではないので、NOを出力して終了します。

ループをすべて通過しても割り切れない場合は、Nが素数であると判定できるので、YESを出力します。

  if N % i == 0:
    print('NO')
    exit()
print('YES')

解答

import math
# 入力
N=int(input())

# ルート N まで割り切れるか判定する
for i in range(2, int(math.sqrt(N)) + 1):
  if N % i == 0:
    print('NO')
    exit()
print('YES')