如果您参与竞争性编程，您可能会熟悉与Prime数相关的问题是问题设定者的选择之一。在这里，我们将讨论如何优化您的函数，该函数检查给定范围集中的Prime数，并且还将计算执行它们的时间。按照定义，Prime数是一个正整数，只能由自身和1整除。
- 例如：2,3,5,7。但是，如果一个数字可以被分解为较小的数字，则称为复合数。
- 例如：4 = 2 * 2,6 = 2 * 3
- 整数1既不是素数也不是复数。检查数字是否为素数很容易，但有效检查需要一些努力。
方法1
现在让我们使用第一个函数来检查数字（例如n）是否为素数。在这种方法中，我们将测试从2到n-1的所有除数。我们将跳过1和n。如果n可被任何除数整除，则该函数将返回False，否则返回True。
以下是此方法中使用的步骤：
- 如果整数小于等于1，则返回False。
- 如果给定的数字可以被2到n中的任何数字整除，则该函数将返回False
- 否则它将返回True
# Python Program to find prime numbers in a range
import time
def is_prime(n):
if n <= 1:
return False
for i in range(2,n):
if n % i == 0:
return False
return True
# Driver function
t0 = time.time()
c = 0 #for counting
for n in range(1,100000):
x = is_prime(n)
c += x
print("Total prime numbers in range :", c)
t1 = time.time()
print("Time required :", t1 - t0)
输出
总质数范围：9592
所需时间：60.702312707901
在上面的代码中，我们检查从1到100000的所有数字，无论这些数字是否为素数。它具有如图所示的巨大运行时间。运行大约需要1分钟。这是一种简单的方法，但需要花费大量时间才能运行。因此，它在竞争性编程中不是首选。
方法2
在这种方法中，我们通过减少我们检查的除数的数量来使用一个简单的技巧。我们发现有一条细线充当镜子，显示线下方的因子分解和线上方的因子分解正好相反。将因子分成两半的线是数字的平方根的线。如果数字是一个完美的正方形，我们可以将线移1，如果我们可以得到划分的线的整数值。
36 = 1 * 36
= 2 * 18
= 3 * 12
= 4 * 9
------------
= 6 * 6
------------
= 9 * 4
= 12 * 3
= 18 * 2
= 36 * 1
在这个函数中，我们计算一个整数，比如max_div，它是数字的平方根，并使用Python的数学库得到它的最低值。在最后一个例子中，我们从2迭代到n-1。但在这方面，如图所示，我们将除数减少了一半。您需要导入数学模块以获得楼层和sqrt功能。
以下是此方法中使用的步骤：
- 如果整数小于等于1，则返回False。
- 现在，我们将需要检查的数字减少到给定数字的平方根。
- 如果给定的数字可以被2到该数字的sqaure根中的任何数字整除，则该函数将返回False
- 否则它将返回True
# Python Program to find prime numbers in a range
import math
import time
def is_prime(n):
if n <= 1:
return False
max_div = math.floor(math.sqrt(n))
for i in range(2, 1 + max_div):
if n % i == 0:
return False
return True
# Driver function
t0 = time.time()
c = 0 #for counting
for n in range(1,100000):
x = is_prime(n)
c += x
print("Total prime numbers in range :", c)
t1 = time.time()
print("Time required :", t1 - t0)
输出
总质数范围：9592
所需时间：0.4116342067718506
⏡⏡在上面的代码中，我们检查从1到100000的所有数字，无论这些数字是否为素数。它比以前的方法花费的时间相对较短。这是一个有点棘手的方法，但在代码的运行时间方面有很大的不同。因此，它在竞争性编程中更为优选。
方法3
⏡⏡现在，我们将代码优化到下一级别，这比前一种方法花费的时间更短。您可能已经注意到，在最后一个示例中，我们遍历每个偶数，直到极限，这是浪费。要注意的是除了两个以外的所有偶数都不能是素数。在这种方法中，我们踢出所有偶数以优化我们的代码，并且只检查奇数除数。
以下是此方法中使用的步骤：
- 如果整数小于等于1，则返回False。
- 如果数字等于2，则返回True。
- 如果数字大于2且可被2整除，则它将返回False。
- 现在，我们检查了所有偶数。现在，寻找奇数。
- 如果给定的数字可以从跳过所有偶数的数字的3到平方根中的任何数字整除，则该函数将返回False
- 否则它将返回True
# Python Program to find prime numbers in a range
import math
import time
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n > 2 and n % 2 == 0:
return False
max_div = math.floor(math.sqrt(n))
for i in range(3, 1 + max_div, 2):
if n % i == 0:
return False
return True
# Driver function
t0 = time.time()
c = 0 #for counting
for n in range(1,100000):
x = is_prime(n)
c += x
print("Total prime numbers in range :", c)
t1 = time.time()
print("Time required :", t1 - t0)
输出
总质数范围：9592
所需时间：0.23305177688598633
⏡⏡在上面的代码中，我们检查从1到100000的所有数字，无论这些数字是否为素数。它比所有以前运行程序的方法花费的时间相对较短。检查素数是最有效和最快捷的方法。因此，它在竞争性编程中是最优选的。下次在竞争性编程中尝试任何问题时，请使用此方法以获得最佳结果。
筛选方法
此方法打印小于或等于给定数量n的所有素数。例如，如果n为10，则输出应为“2,3,5,7”。如果n为20，则输出应为“2,3,5,7,11,13,17,19”。
该方法被认为是生成小于给定数量n的所有素数的最有效方法。它被认为是生成素数列表的最快方法。此方法不适合检查特定数字。该方法优选用于生成所有素数的列表。
# Python Program to find prime numbers in a range
import time
def SieveOfEratosthenes(n):
# Create a boolean array "prime[0..n]" and
# initialize all entries it as true. A value
# in prime[i] will finally be false if i is
# Not a prime, else true.
prime = [True for i in range(n+1)]
p = 2
while(p * p <= n):
# If prime[p] is not changed, then it is
# a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p * 2, n + 1, p):
prime[i] = False
p += 1
c = 0
# Print all prime numbers
for p in range(2, n):
if prime[p]:
c += 1
return c
# Driver function
t0 = time.time()
c = SieveOfEratosthenes(100000)
print("Total prime numbers in range:", c)
t1 = time.time()
print("Time required:", t1 - t0)
输出：
总质数范围：9592
所需时间：0.0312497615814209
注意：所有过程所需的时间可能因编译器而异，但不同方法所需的时间顺序将保持不变。
网友评论