分析在 Python 中查找素数的不同方法
pythonserver side programmingprogramming更新于 2025/10/18 16:44:17
素数是只能被 1 或自身整除的正整数。长期以来，查找数字是否为素数是一项有趣的编程挑战。此外，还有不同的方法，它们的效率也不同。在本文中，我们将研究三种这样的方法，并判断哪一种方法在执行时间方面更有效率。
检查所有除数
这是一个简单的程序，我们取从 1 到小于给定数字的每个整数，并不断检查该数字是否被其中任何一个除以。如果没有找到可以整除该数字的数字，则该数字为素数。
示例
import time #检查素数的函数 def check_prime(final_val): if final_val <= 1: return False for divisor in range(2,final_val): if final_val % divisor == 0: return False return True # 追踪开始时间 StartTime = time.time() #计算素数的数量 cnt = 0 for final_val in range(1,10001): x = check_prime(final_val) cnt += x print 'Count of prime numbers till',final_val,'is ', cnt # 追踪结束时间 EndTime = time.time() print 'Time Elapsed is: ', EndTime - StartTime
输出
运行上述代码得到以下结果 −
Count of prime numbers till 10000 is 1229 Time Elapsed is: 2.3100001812
直到平方根的因数(N)
从数学上讲，我们还可以发现，找到我们要检查的数字的直到平方根的因数就足够了。这种方法减少了迭代次数，因此应该更快，我们可以按如下方式进行检查。实现这个想法的逻辑如下。
我们找出要检查是否为素数的数字的平方根。
我们从值 2 开始用直到平方根的每个值除以该数字，以检查是否还有余数。
如果上述任何步骤中剩余的余数为零，则该数字不是素数。
示例
import math import time def is_prime(final_val): # 1 is not a prime number if final_val <= 1: return False i = 2 while i <= math.floor(math.sqrt(final_val)): # Check if any remainders are cerated if final_val % i == 0: return False i += 1 return True # 追踪开始时间 StartTime = time.time() cnt = 0 for n in xrange(1, 10001): x = is_prime(n) cnt += x print 'Count of prime numbers till',n,'is ', cnt # 追踪结束时间 EndTime = time.time() print 'Time Elapsed is: ', EndTime - StartTime
输出
运行上述代码得到以下结果 −
Count of prime numbers till 10000 is 1229 Time Elapsed is: 0.0529999732971
埃拉托斯特尼筛法
在此方法中，我们消除非素数或合数以获得素数，直到特定数字。因此，下面是我们为实现此目标所遵循的步骤。
列出从 2 到我们想要找到所有素数的数字的连续整数列表。
取第一个数字，即 2，并创建其所有倍数的列表。从原始列表中消除此倍数列表，但不消除 2。对下一个数字，即 3 重复此操作，依此类推。请注意，我们只消除倍数，而不是数字本身。因此 5 或 11 永远不会被消除，但 10 和 22 会被消除。
在完成所有消除后，剩下的列表就是素数列表，直到所要求的数字。
示例
import time def sieve_method(n): #创建素数列表 prime_number_list = [] for i in range(2, n+1): # 如果数字不在素数列表中，则捕获该数字 if i not in prime_number_list: print (i) # 如果数字是倍数，则将其添加到素数列表数字中 for j in range(i*i, n+1, i): prime_number_list.append(j) # 跟踪开始时间 StartTime = time.time() cnt = 0 print(sieve_method(25)) # 跟踪结束时间 EndTime = time.time() print 'Time Elapsed is: ', EndTime - StartTime
输出
运行上述代码得到以下结果 −
2 3 5 7 11 13 17 19 23 Time Elapsed is: 0.0
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
