在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