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

Question

任务是从 www.codewars.com提取的

素数没有固定的间隔。例如，从2到3，步骤1。从3到5，步骤2。从7到11，是4。在2到50之间，我们有以下两步素数： 3，5-5，7，- 11，13，- 17，19，- 29，31，- 41，43 我们将编写一个带有参数的函数步骤： G(整数>= 2)表示我们正在寻找的步骤， M(整数>= 2)，给出搜索的开始(m包括在内)， N(整数>= m)，给出搜索结束(n包括在内) 在上面的例子中，步骤( 2，2，50)将返回3，5，这是第一对2到50之间的2步。 因此，这个函数应该返回两个质数中的第一对，在限值m，n之间间隔了一步，如果这些g-步骤素数不存在，则为零、空、零或零，或[]或"0，0“或{0，0}或0(取决于语言)。 例子:步骤(2，5，7) -> 5，7或(5，7)或{5，7}或"5 7“ 步骤(2，5，5) ->零或.或[]在Ocaml或{0，0}在C++中 步骤(4,130,200) -> 163,167或(163,167)或{163,167} 请参阅更多“测试”中的语言示例。 备注：(193,197也是这样的四步素数在130到200之间，但这不是第一对)。 步骤(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]]

如果您有任何建议甚至示例代码，我会很感激的.

Answer 1

首先，从不使用关键字作为变量。

要想找到一个更好的方法，你需要考虑你的方法中的缺陷。

1. 你在迭代所有的数字来确定素数。
2. 您正在遍历O(n**2)中的列表，以确定一对是否存在所需的差异。
3. 您的素数计算算法不是最优的。

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

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

关于第三点，您可以在维基百科页面本身找到一个最佳实现。如果您能够理解逻辑，那么您可以很容易地自己编写该实现。

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

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)，这个实现只需1.32秒进行1,000,000次迭代。正如您所看到的，一旦实现了is_prime函数，逻辑就非常简单。