在Python程序中查找素数的不同方法的分析

在本教程中，我们将看到不同的方法来查找每种方法所需的质数和时间。我们将使用时间模块来计算执行时间。

方法1

这是查找质数的一般方法。

• 如果数字小于或等于1，则返回False。

• 如果数字可被任何数字整除，则该函数将返回False。

• 循环后，返回True。

示例

# importing time module
import time
# checking for prime
def is_prime(n):
   if n <= 1:
      return False
   else:
      for i in range(2, n):
         # checking for factor
         if n % i == 0:
            # return False
            return False
      # returning True
      return True
# starting time
start_time = time.time()
primes = 0
for i in range(100000):
   if is_prime(i):
      primes += 1
print(f'Total primes in the range {primes}')
# ending time
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

输出结果

如果运行上面的程序，您将得到以下结果。

Total primes in the range 9594
Execution time: 63.1301212310791

方法2

在这种方法中，我们通过将迭代次数切成n的平方根来减少迭代次数。

让我们看一下代码。

示例

# importing time module
import time
# importing math module for sqrt function
import math
# checking for prime
def is_prime(n):
   if n <= 1:
      return False
   else:
      # iterating loop till square root of n
      for i in range(2, int(math.sqrt(n)) + 1):
         # checking for factor
         if n % i == 0:
            # return False
            return False
      # returning True
      return True
# starting time
start_time = time.time()
primes = 0
for i in range(100000):
   if is_prime(i):
      primes += 1
print(f'Total primes in the range {primes}')
# ending time
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

输出结果

如果运行上面的程序，您将得到以下结果。

Total primes in the range 9592
Execution time: 0.2039644718170166

方法3

在前面的方法中，我们检查了偶数。我们都知道，偶数除两个外都不是质数。因此，在此方法中，我们将删除所有偶数以减少时间。

示例

# importing time module
import time
# importing math module for sqrt function
import math
# checking for prime
def is_prime(n):
   # checking for less than 1
   if n <= 1:
      return False
   # checking for 2
   elif n == 2:
      return True
   elif n > 2 and n % 2 == 0:
      return False
   else:
      # iterating loop till square root of n
      for i in range(3, int(math.sqrt(n)) + 1, 2):
         # checking for factor
         if n % i == 0:
            # return False
            return False
      # returning True
      return True
# starting time
start_time = time.time()
primes = 0
for i in range(100000):
   if is_prime(i):
      primes += 1
print(f'Total primes in the range {primes}')
# ending time
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

输出结果

如果运行上面的程序，您将得到以下结果。

Total primes in the range 9592
Execution time: 0.10342741012573242

结论