时间戳

首页 > 解决方案 > 如何改进此代码以提高时间效率？For循环，素数

python - 如何改进此代码以提高时间效率？For循环，素数

问题描述

该任务来自www.codewars.com

素数不是规则间隔的。例如，从 2 到 3，步长为 1。从 3 到 5，步长为 2。从 7 到 11，步长为 4。在 2 到 50 之间，我们有以下成对的 2 步素数：

3, 5 - 5, 7, - 11, 13, - 17, 19, - 29, 31, - 41, 43

我们将编写一个带参数的函数步骤：

g (integer >= 2) 表示我们正在寻找的步骤，

m (integer >= 2) 给出搜索的开始（包括 m），

n (integer >= m) 结束搜索（n 包括在内）

在上面的示例中， step(2, 2, 50) 将返回 [3, 5] ，它是 2 到 50 之间的第一对，有 2 步。

所以这个函数应该返回两个素数中的第一对，在限制 m 之间间隔 g 步长，如果这些 g 步长素数存在，则 n 否则为 nil 或 null 或 None 或 Nothing 或 [] 或 "0, 0"或 {0, 0} 或 0 0（取决于语言）。

示例：step(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7} or "5 7"

step(2, 5, 5) --> nil or ... or [] in Ocaml or {0, 0} in C++

step(4, 130, 200) --> [163, 167] 或 (163, 167) 或 {163, 167}

在“测试”中查看您的语言的更多示例

备注：（[193, 197] 也是 130 到 200 之间的这样一个 4 步素数，但它不是第一对）。

step(6, 100, 110) --> [101, 107] 虽然在 101 和 107 之间有一个素数，即 103；101-103 对是 2 步。

这是我的解决方案，它运行良好，并且比测试所需的更多，但是，我正在尝试优化此代码以使其更省时。

def step(g,m,n):

    count = 0
    list= []
    list2 = []
    for num in range(m,n+1):
        if all(num%i!=0 for i in range(2,num)):
            count += 1
            list.append(num)
    

        
    for k in list:
        for q in list:
            if (q-k) > 0:
                if (q-k) == g:
                    list2.append(k)
                    list2.append(q)
            

                
    if not list2:
         return 
    else:
         return  [list2[0],list2[1]]

如果您有任何建议甚至示例代码，我将不胜感激。

标签： pythonlistfor-loopif-statementprimes

解决方案

首先，永远不要使用关键字作为变量。

要采用更好的方法，您需要考虑方法中的缺陷。

  1. 您正在遍历所有数字以确定素数。
  2. 您正在遍历 O(n**2) 中的列表以查找是否存在具有所需差异的对。
  3. 您的素数计算算法不是最佳的。

对于第一点，甚至不需要找到给定范围内的所有素数，因为您的任务是找到具有所需差异的第一对。因此，如果您发现数字 a既是素数a + g又是素数，那么您已经找到了解决方案。

对于第二点，您可以简单地遍历列表，并检查if (k + g) in list是否找到了该对。

对于第三点，您可以在 wikipedia 页面本身上找到最佳实现。如果你能理解逻辑，那么你可以很容易地自己编写那个实现。

因此，将最佳素数检查实现与单个循环迭代相结合，可以轻松编写解决方案，如下所示。

from functools import lru_cache

@lru_cache(None)
def is_prime(n):
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True


def step(g, m, n):
    for i in range(m, n + 1 - g):
        if is_prime(i) and is_prime(i + g):
            return [i, i + g]
    return

对于step(4, 130, 200). 如您所见，一旦实现该is_prime功能，逻辑就非常简单。

推荐阅读