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