与えられたNが素数かどうか判定するアルゴリズム
\(2\sim N-1\)でひたすら割る
\(i=2, 3, 4, …, 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))
print(1000, is_prime_number(1000))
print(9874633, is_prime_number(9874633))13 True
1000 False
9874633 True\(2\sim\sqrt{N}\)で割る(試し割法)
素数か判定するには下記の理由で\(2~\sqrt{N}\)のいずれで割ってもNが割り切れないことを確認すれば十分。
- Nが素数でないと仮定すると、整数a, bを使って\(a \times b\)で表すことができる。
- \(a \leq b\)である場合、Nはaもしくはaの約数で割ることができる。
- この時aは\(a \leq \sqrt{N}\)であるため、\(2\sim\sqrt{N}\)のいずれかで割ることができるはずである。
- したがって\(2~\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))
print(1000, is_prime_number(1000))
print(9874633, is_prime_number(9874633))13 True
1000 False
9874633 True
コメント