Python是數位檢查器演算法
使用 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$）必須小於或等於$n$ 的平方根。因此，檢查更高的值是多餘的。