Разрыв в простых числах (Codewars) - вне времени

Вы можете полностью исключить вторую часть с помощью списка чисел, отслеживая расстояние между простыми числами в решето логики Эратосфена. Кроме того, вы можете инициализировать свой список простых чисел с уже отброшенными числами, кратными двум, а затем шаг за шагом проверять простые числа после 2 и правило 6 после 5.

Вы можете обновить кратные простых чисел с помощью

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

Обратите внимание, что это медленнее (в 2 раза), чем сито, когда разрыв не обнаружен раньше (до n / 4), поэтому вам следует придерживаться оптимизированной функции 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

[EDIT] обход тайм-аута ...

Кажется, проблема заключается в регенерации простых чисел при каждом тесте. Если вы создадите список простых чисел в глобальной переменной (вне функции) и используете его для поиска пробелов в функции, вы не получите тайм-аут.

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] еще более быстрое решение ...

Учитывая, что ожидание (или допустимый подход) состоит в том, чтобы подготовить глобальные переменные, мы могли бы пойти еще дальше и создать словарь простых списков с ключами на пробелах. Затем функция могла бы использовать двоичный поиск mв списке, соответствующем, gи найти результат за 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]

Это зависит от вашего лимита времени. Простая оптимизация, которая, тем не менее, дает такую ​​же вычислительную сложность, - это избегать копирования найденных простых чисел в новый вектор.

Используя prime, вы можете перебирать массив, используя «окно» длины g. начиная с m, вы проверяете, является ли m простым и простым ли m + g. Если да, то Бинго! В противном случае вы перейдете к 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)