素数判定
与えられた \(N\) が素数かどうか判定するアルゴリズム。
\(2 \sim N-1\) でひたすら割る
\(i=2, 3, 4, \ldots, N-1\) のいずれで割っても \(N\) が割り切れないことを確認する。
計算量は \(O(N)\)。
def is_prime_number(n: int):
for i in range(2, n):
if n % i == 0:
return False
return True
if __name__ == "__main__":
print(13, is_prime_number(13)) # 13 True
print(1000, is_prime_number(1000)) # 1000 False
print(9874633, is_prime_number(9874633)) # 9874633 True
\(2 \sim \sqrt{N}\) で割る（試し割法）
素数か判定するには \(2 \sim \sqrt{N}\) のいずれで割っても \(N\) が割り切れないことを確認すれば十分。
理由：
- \(N\) が素数でないと仮定すると、整数 \(a, b\) を使って \(a \times b\) で表すことができる。
- \(a \leq b\) である場合、\(N\) は \(a\) もしくは \(a\) の約数で割ることができる。
- このとき \(a \leq \sqrt{N}\) であるため、\(2 \sim \sqrt{N}\) のいずれかで割ることができるはずである。
- したがって \(2 \sim \sqrt{N}\) で割り切れなければ、1の仮定が誤っている、つまり \(N\) が素数であることが確認できる。
この方法での計算量は \(O(\sqrt{N})\)。
import math
def is_prime_number(n: int):
for i in range(2, math.ceil(math.sqrt(n))):
if n % i == 0:
return False
return True
if __name__ == "__main__":
print(13, is_prime_number(13)) # 13 True
print(1000, is_prime_number(1000)) # 1000 False
print(9874633, is_prime_number(9874633)) # 9874633 True