质数的差距(Codewar)-超时

Question

问:质数之间的间隔不是规则的。例如，从2到3的间隙是1。从3到5的间隙是2。从7到11的间隙是4。在2到50之间，我们有以下两对2-间隙素数: 3-5，5-7，11-13，17-19，29-31，41-43

长度为n的素数间隙是两个连续素数之间的n-1个连续合成数的游程(参见：http://mathworld.wolfram.com/PrimeGaps.html)。

我们将写一个带参数的函数间隙：

G (integer >= 2)，它表示我们正在寻找的间隙

M(整数> 2)，给出搜索的开始(包括m)

N(整数>= m)，表示搜索结束(包括n)

N不会超过1100000。

在上面的示例中，gap(2，3，50)将返回3，5或(3，5)或{3，5}，这是3和50之间的第一个具有2-gap的对。

因此，此函数应返回第一对两个质数，如果这些数字存在‘`nil or null或None或Nothing (或...取决于语言)。

# My attempt
def gap(g, m, n):
    prime = [True for _ in range(n+1)]
    p = 2
    
    while (p*p <= n):
        if prime[p]:
            for i in range(p*p, n+1, p):
                prime[i] = False
        p += 1
        
    nums = [i for i, T in enumerate(prime) if T and i>m]
    
    for i in range(len(nums)-1):
        if nums[i+1] - nums[i] == g:
            return [nums[i], nums[i+1]]
        
    else: return

我的函数在较小的数字中工作得很好，但是当它超过6位数时，它就超时了。我可以在哪里改进我的代码？

Answer 1

你可以通过在你的Eratosthenes逻辑筛子中跟踪素数之间的距离来消除数字列表中的整个第二部分。此外，您可以使用已经丢弃的2的倍数来初始化素数列表，然后逐个2来检查2之后的素数和5之后的6的规则。

您可以使用以下命令更新质数的倍数

primes[p*p::2*p] = [False]*len(range(p*p,len(primes),2*p))

而不是for循环。

下面是优化后的版本：

def gap(g, m, n):
    isPrime = [False,False,True]+[True,False]*(n//2)
    prev,p,inc = 2,3,2    
    while p<=n:
        if isPrime[p]:
            isPrime[p*p::2*p] = [False]*len(range(p*p,len(isPrime),2*p))
            if prev>=m and p-prev == g:
                return prev,p
            prev = p
        p,inc = p+inc,2 if p<5 else (6-inc)

就我个人而言，我会以不同的方式处理这个问题。我将首先创建一个生成素数的生成器函数。然后，我将使用这个生成器函数来获取素数，跟踪一个与下一个之间的差异，并返回第一个合格的对：

def primeGen(maxPrime):   # primes generator, up to maxPrime
    skip = dict()
    yield 2
    p = 1
    while p<=maxPrime:
        p += 2
        if p not in skip:
            yield p
            if p*p<maxPrime: skip[p*p] = 2*p
            continue
        step = skip.pop(p)
        mult = p + step
        while mult in skip: mult += step
        skip[mult] = step

def primeGap(g,m,n):
    previous = None
    for prime in primeGen(n):
        if prime<m: continue
        if previous and prime-previous == g:
            return previous,prime
        previous = prime

请注意，当没有及早(在n/4之前)发现间隙时，这比筛子慢(2倍)，所以如果执行时间有限，您应该坚持使用优化的gap()函数

输出：

print(primeGap(2,3,50))        # (3,5)
print(primeGap(4,3,50))        # (7,11)
print(primeGap(6,3,50))        # (23,29)
print(primeGap(8,1000,2000))   # (1109, 1117)     
print(primeGap(48,1,1100000))  # (28229, 28277)    6.5 milliseconds
print(primeGap(100,1,1100000)) # (396733, 396833) 79.5 milliseconds

编辑超时的解决方法...

似乎问题是在每次测试中重新生成素数。如果您在全局变量(函数外部)中创建一个质数列表，并将其用于函数中的间隙搜索，那么您将不会得到超时。

primes   = [2]     
maxPrime = 1100000
isPrime = [False,False,True]+[True,False]*(maxPrime//2)
p,inc = 3,2    
while p<=maxPrime:
    if isPrime[p]:
        primes.append(p)
        isPrime[p*p::2*p] = [False]*len(range(p*p,len(isPrime),2*p))
    p,inc = p+inc,2 if p<5 else (6-inc)

def gap(g, m, n):
    prev = None
    for p in primes:
        if p>n: break
        if p<m: continue
        if prev and p-prev == g: return [prev,p]
        prev = p

EDIT2更快的解决方案...

考虑到期望(或所有方法)是准备全局变量，我们可以更进一步，根据差距建立质数列表的字典。然后，该函数可以在对应于g的列表中对m进行二进制搜索，并在logN时间内找到结果。总体上，这至少比之前通过素数进行顺序搜索的解决方案快了2倍。设置字典后，gap()函数在7微秒内返回结果。

gaps    = dict()
maxPrime = 1100000
isPrime = [False,False,True]+[True,False]*(maxPrime//2)
prev,p,inc = 2,3,2    
while p<=maxPrime:
    if isPrime[p]:
        isPrime[p*p::2*p] = [False]*len(range(p*p,len(isPrime),2*p))
        gapFirst,gapNext = gaps.setdefault(p-prev,[[],[]])
        gapFirst.append(prev)
        gapNext.append(p)
        prev=p
    p,inc = p+inc,2 if p<5 else (6-inc)

from bisect import bisect_left
def gap(g, m, n):
    gapFirst,gapNext = gaps.get(g,[[],[]])     # pairs for gap of 'g'
    i = bisect_left(gapFirst,m)                # binary search, >= m
    if i < len(gapFirst) and gapNext[i] <= n:
        return [ gapFirst[i], gapNext[i] ]     # Found first gap in [m...n]

Answer 2

这取决于你的时间限制是什么。一种简单的优化方法是避免将找到的素数复制到新的向量中，但这会产生相同的计算复杂性。

使用prime，您可以使用长度为g的“窗口”遍历数组。从m开始，检查m是否为质数，m + g是否为质数。如果是，那么Bingo！否则，您将转到m + 1。

您可以在以下代码中看到这一点

import time

def original_gap(g, m, n):
    prime = [True for _ in range(n + 1)]
    p = 2

    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1

    nums = [i for i, T in enumerate(prime) if T and i >= m]

    for i in range(len(nums)-1):
        if nums[i + 1] - nums[i] == g:
            return [nums[i], nums[i + 1]]

    return

def new_gap(g, m, n):
    if g > n - m:
        return None

    prime = [True for _ in range(n + 1)]
    p = 2

    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1

    for index in range(m, n - g + 1):
        if prime[index] and prime[index + g]:
            return [index, index + g]

    return None

if __name__ == "__main__":
    start = time.time()
    print(new_gap(2, 3, 1100000))
    end = time.time()
    print("Time for 3-1100000 is: ", end - start)

    start = time.time()
    print(original_gap(2, 3, 1100000))
    end = time.time()
    print("Time for 3-1100000 is: ", end - start)