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$ 的平方根。因此，检查更高的值是多余的。