Как оптимизировать код для нахождения простых чисел (Задачка из CodeWars)?

Question

[Archie_7]

Постигаю науку по изучению алгоритмов. Для этого решаю задачки на CodeWars.
Цель именно этой задачи - выдать первую пару соседних простых чисел, разность которых будет равна определенному значению (g), в промежутке от m до n, где g, m и n могут быть следующими:
g >=2, m>2, n<=1100000

Моя функция выглядит следующим образом:

def gap(g, m, n):
    a = [x for x in range(n+1)]
    a[1] = 0
    lst = []
    i = 2
    while i <= n:
        if a[i] != 0:
            lst.append(a[i])
            for j in range(i, n+1, i):
                a[j] = 0
            if i >= m+g and (lst[-1]-lst[-2] == g):
                return [lst[-2], lst[-1]]
        i +=1
    return None

У меня на PC все работает довольно быстро. Даже при 30-кратном увеличении максимального n, программа успевает все просчитать менее чем за 12 секунд. При n=1100000, просчет завершается за 0.35 секунды.
Тем не менее, тест Attempt я пройти не могу (Execution Timed Out (12000 ms)). Кажется я просто не понимаю, как устроены эти тесты)

Comments

[alexbprofit]

Тесты на codewars устроены таким образом что ты проверяешь не ОДИН случай а несколько сотен, + еще тратится примерно секунда на доп расчеты

Answer 1

[alexbprofit]

def isPrime(n):
 
    # Corner case
    if (n <= 1):
        return False
 
    # Check from 2 to sqrt(n)
    for i in range(2, int(n**.5)+1):
        if (n % i == 0):
            return False
 
    return True

def gap(distance, range_lower, range_upper):
  worked_area = list(range(range_lower,range_upper+1))

  find_primes = [el for el in worked_area if isPrime(el)]
  if len(find_primes) == 0:
    return []

  for i in range(1, len(find_primes)):
    if find_primes[i] - find_primes[i-1] == distance:
      return [find_primes[i-1], find_primes[i]]

  return []

Или:

def isPrime(n):
 
    # Corner case
    if (n <= 1):
        return False
 
    # Check from 2 to sqrt(n)
    for i in range(2, int(n**.5)+1):
        if (n % i == 0):
            return False
 
    return True

def gap(g, m, n):
    start = 0
    end = 0
    for i in range(m,n+1):
      if isPrime(i):
        if start == 0:
          start = i
        elif end == 0:
          end = i
        else:
          start = end
          end = i
      if end - start == g:
        return [start, end]
    return None

Answer 2

[Andrey]

как вариант

spoiler

def simple_numbers(m, n):
    for i in range(m, n):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            yield i


def test(g, m, n):
    lst = []
    for i in simple_numbers(m, n):
        lst.append(i)
        if len(lst)>1:
            if abs(lst[-1] - lst[-2]) == g:
                return [lst[-1], lst[-2]]
    return False

g = 6
m = 2
n = 1100000
rez = test(g, m, n)

if rez:
    print("{} - {} = {}".format(rez[0], rez[1], g))
else:
    print("No")