Python Prime チェッカー アルゴリズム
Python を使用して数値が素数かどうかを確認します。インタラクティブなアルゴリズムを実行して、効率的な数学的反復とルート評価を確認します。
概要
素数とは、1 とそれ自体以外に正の約数を持たない、1 より大きい正の整数です。
素数をチェックする最も非効率的な方法は、数値そのものまで繰り返すことです。強力な最適化は、数値の平方根までの割り算のみをチェックすることです。
コードと実行の出力
O(sqrt(n)) の最適化を示す効率的な素数チェック アルゴリズム。
prime_checker.py
エディターで試してみるimport math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
max_divisor = math.isqrt(n)
for i in range(3, max_divisor + 1, 2):
if n % i == 0:
return False
return True
test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
status = "Prime" if is_prime(num) else "Not Prime"
print(f"{num:2d} -> {status}")端子出力
2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> Prime段階的な実装
- 暗号化およびハッシュアルゴリズム
- 教育数学とふるい理論
- 安全なキーのバックエンド検証
よくある質問
なぜ平方根までしかチェックしないのでしょうか?
$n = a \times b$ の場合、因数 ($a$ または $b$) の少なくとも 1 つは $n$ の平方根以下でなければなりません。したがって、上位をチェックすることは冗長です。