ruby ​​- Быстрый поиск пробела

Question

Я работаю над созданием метода, зазора (g, m, n).

Все 3 параметра являются целыми числами.

---

Зазор обнаруживает первые два последовательных простых числа между m и n, которые имеют разность g.

Например, зазор (2, 1, 10) => [3, 5]

В диапазоне от т до п, 1..10, первые 2 последовательных простых чисел с зазором 2 - [3,5].

Если вместо этого, он был зазор (1, 1, 10) => [2,3]

и если это был зазор (6, 1, 10) => NIL

https://repl.it/BbGo/1

---

# method to check if a number is prime 

def prime?(num) 
    (2..Math.sqrt(num).floor).each do |m| 
    if num % m == 0 
     return false 
    end 
    end 
    true 
end 

этот метод работает путем перебора каждого числа от 2, наименьшее простое число, к корню квадратному из параметра, проверяя, если параметр нацело на что-нибудь в этом диапазоне. Если это так, метод возвращает false.

---

# gap method 
def gap(g, m, n) 

    if g.odd? && g > 1 
    return nil 
    end 

    primes = (m..n).select do |num| 
       num.odd? && prime?(num) 
      end 

    first = primes[0..-2].find_index do |x| 
       primes[primes.index(x) + 1] - x == g 
      end 

    [ 
    primes[first], 
    primes[first+1] 
    ] unless first.nil? 

end 


gap(2, 10000000, 11000000) 

Все простые числа имеют разрыв либо 2, 4, или номер, состоящий из 2 и 4-х вместе добавил. Единственным исключением является разрыв с 2-3.

Таким образом, если аргумент gap, g, задан как 3, который является нечетным и больше 1, метод автоматически возвращает nil, потому что такой простой разрыв отсутствует.

---

Проблема

Моя проблема заключается в том, что метод является слишком медленным. Используя ссылку на реплику выше, вы получаете время около 20 секунд. По-видимому, его можно получить примерно на 1 секунду.

Я попытался оптимизировать, отфильтровывая четные числа уже с m..n, что помогло. Но я просто не уверен, как я могу добиться этого еще быстрее.

Я думаю, что прежде чем обнаруживать каждое простое число в m..n, я должен проверять каждую итерацию, если пробел правильный, поэтому, как только я нахожу это, я могу просто прекратить метод, не глядя на ненужные простые числа , но я не уверен, как это реализовать.

Спасибо за помощь, и любая общая критика моего кода также приветствуется.

Answer 1

ответа с помощью советов Иордании:

def gap(g, m, n) 

    if g.odd? && g > 1 
    return nil 
    end 

    recent = 0 
    current = 0 

    (m..n).each do |num| 
    if num.odd? && prime?(num) 
     current = num 
     if current - recent == g 
     break 
     else 
     recent = current 
     end 
    end 
    end 

    [recent, current] unless current - recent != g 

end 

gap(2, 10000000, 11000000) 
#=> [10000139, 10000141] 

завершается в 3 мс.

https://repl.it/BbGo/3

Спасибо!