在Python中查找素数的不同方法的分析
质数是一个只能被1或自身整除的正整数。长期以来，查找数字是否为质数是一个有趣的编程挑战。而且，方法不同，效率也不同。在本文中，我们将研究三种这样的方法，并判断哪种方法在执行时间上更有效。
检查所有除数
这是一个简单的程序，我们将每个整数从给定的数字中减去1到一个，然后继续检查该数字是否除以其中的任何一个。如果未找到可以除以该数字的数字，则该数字为质数。
示例
import time
#Function to check Prime Number
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
# Track the Start Time
StartTime = time.time()
#Count the number of prime numbers
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
# Track the End Time
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
# Track the Start Time
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
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime输出结果
运行上面的代码给我们以下结果-
Count of prime numbers till 10000 is 1229 Time Elapsed is: 0.0529999732971
Eratosthenes筛
在这种方法中，我们消除了非素数或合成数，以得到素数直到一个特定的数。因此，以下是我们为实现该目标而应遵循的步骤。
列出从2到该数字的连续整数，直到找到所有质数为止。
以第一个数字（即2）创建所有倍数的列表。从原始列表中消除此倍数列表，但不删除2。对下一个数字重复此操作，即对下一个数字重复3，依此类推。请注意，我们仅消除了倍数，而不消除了数字本身。因此5或11不会被淘汰，而10和22会被淘汰。
在所有消除之后，剩下的列表是素数列表，直到要求的数字为止。
示例
import time
def sieve_method(n):
#Create a list of prime numbers
prime_number_list = []
for i in range(2, n+1):
# Capture the number if it si not in prime list
if i not in prime_number_list:
print (i)
# Add the number to the prime list number if it is a multiple
for j in range(i*i, n+1, i):
prime_number_list.append(j)
# Track the Start Time
StartTime = time.time()
cnt = 0
print(sieve_method(25))
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime输出结果
运行上面的代码给我们以下结果-
2 3 5 7 11 13 17 19 23 Time Elapsed is: 0.0