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

0

Вопрос: Простые числа не расположены равномерно. Например, от 2 до 3 пробел равен 1. От 3 до 5 пробел равен 2. От 7 до 11 это 4. Между 2 и 50 у нас есть следующие пары простых чисел с двумя пробелами: 3-5, 5-7 , 11-13, 17-19, 29-31, 41-43

Промежуток между простыми числами длины n - это последовательность n-1 последовательных составных чисел между двумя последовательными простыми числами (см. Http://mathworld.wolfram.com/PrimeGaps.html ).

Напишем функциональный пробел с параметрами:

g (целое число> = 2), что указывает на пробел, который мы ищем

m (целое число> 2), что дает начало поиска (m включительно)

n (целое число> = m), которое дает конец поиска (n включительно)

n не выйдет за пределы 1100000.

В приведенном выше примере пробел (2, 3, 50) вернет [3, 5] или (3, 5) или {3, 5}, который является первой парой между 3 и 50 с пробелом 2.

Таким образом, эта функция должна возвращать первую пару из двух простых чисел, разделенных промежутком g между границами m, n, если эти числа существуют, иначе `nil или 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 цифр, времени не хватает. Где я могу улучшить свой код?

0
1

Вы можете полностью исключить вторую часть с помощью списка чисел, отслеживая расстояние между простыми числами в решето логики Эратосфена. Кроме того, вы можете инициализировать свой список простых чисел с уже отброшенными числами, кратными двум, а затем шаг за шагом проверять простые числа после 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]
5
  • Уоу .. оба решения увеличивают "Время ожидания выполнения (12000 мс)" ... хм, я потерял дар речи. Есть ли какие-то возможности, что причиной этого является более медленный интернет ?! codewars.com/kata/561e9c843a2ef5a40c0000a4/train/python
    Cookie
    вчера
  • Должна быть какая-то проблема с сервером. 12000 мс - это время выполнения 12 секунд. Даже в худшем случае (то есть не найти пару простых чисел до 1100000, на моем ноутбуке требуется всего 66 мс с оптимизированной функцией gap ()). Вряд ли это проблема скорости интернета. вчера
  • Да, я пробовал с ноутбуком jupyter, и все работает нормально. Думаю, я просто пропущу этот :(
    Cookie
    вчера
  • Выяснил обходной путь для проблемы с тайм-аутом, см. ИЗМЕНИТЬ мой ответ. Они должны провести несколько сотен тестов, чтобы оно превысило 12 секунд. вчера
  • Вау, это работает, я все еще как-то не понимаю. Думаю, позже я загляну в библиотеку bisect :(
    Cookie
    16 часов назад
0

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

Используя 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)