up vote 2 down vote favorite
1

This was my solution to a function that should return the first pair of two prime numbers spaced with a gap of g between the limits m, n if these numbers exist otherwise nil.

This is a kata from codewars.com, it passed the preliminary test. But, When I submit it I receive an error message saying that due to an inefficiency in my algorithm it takes too much time(8000ms+).

Can someone point out to me what exactly is slowing down the code, and how it should be optimized?

require 'prime'

def gap(g, m, n)
  range = (m..n).to_a
  primes = []
  range.each { |num| primes.push(num) if Prime.prime?(num)}


  primes.each_index do |count|
    prv , nxt = primes[count], primes[count+1]
    if !nxt.is_a? Integer
      return nil
    end

    if nxt - prv == g
      return [prv, nxt]
    end
  end
end
share|improve this question
    
Thanks for the tips.But, I still get the same error message: Process was terminated. It took longer than 8000ms to complete – Rafael Viana Oct 3 '16 at 5:17
1  
If you're allowed to use the Ruby prime module, I would look for methods in that module that will generate the primes in the range for you, rather than using the prime test on all numbers in the range. Usually such modules are optimized quite a bit better than probably most professional programmers could. One small optimization example, of which there are probably many more and more complicated ones in the module's prime generators, is that you needn't run the prime test on any even numbers (like you are currently doing). – גלעד ברקן Oct 3 '16 at 6:06
    
You might consider en.wikipedia.org/wiki/Sieve_of_Eratosthenes also, do the primes with the specified gap have to be consecutive? – user12341234 Oct 3 '16 at 6:21
    
Do you know for what values of the three arguments the method must take no longer than 8 seconds to complete? – Cary Swoveland Oct 3 '16 at 17:25
up vote 2 down vote accepted

Try this:

require 'prime'

def gap(g, m, n)
  primes = Prime.each(n).select { |p| p >= m }
  primes[0..-2].zip(primes[1..-1]).find { |a, b| b - a == g } 
end

gap(2, 1, 1000)
#=> [3, 5]

gap(6, 1, 1000)
#=> [23, 29]

Prime.each(n).select { |p| p >= m } returns you the list of all primes between m and n. This has a better performance than building an array with all numbers between m and n and the checking each number in this array if it is a prime. It is also worth noting that Prime.each uses the eratosthenes' sieve algorithm as a default.

primes[0..-2].zip(primes[1..-1]) builds an array of each pair. This is not the most efficient way to iterate over each pair in the primes array, but I think it read better than dealing with indexes.

This might be another option:

require 'prime'
require 'set'

def gap(g, m, n)
  primes = Set.new(Prime.each(n).select { |p| p>= m })
  primes.each { |prime| return [prime, prime + g] if primes.include?(prime + g) }
end

the second version doesn't build an new array with all pairs, but instead just checks for each prime if prime + g is included in the primes array too. I use a Set, because it improves include? lookups to O(1) (whereas include? on arrays would be O(n).

I am not sure which version will be faster and it might be worth it to run some benchmarks. The first versions needs more memory, but does less calculations. The performance probably depends on the size of the range.

share|improve this answer
    
Note that the first solution will only find pairs of consecutive primes spaced by the gap. For instance, for g = 6, it will find [23, 29], but not [5, 11]. The second solution will find both. – Amadan Oct 3 '16 at 7:23
    
You are right, @Amadan. I missed this side effect of my optimization. I think it depends on the specification if the second example is even an option. The OP will probably have to use the first version in his example. But I will keep the second version in the answer, because it might help others. premature optimization is the root of all evil --Donald Knuth – spickermann Oct 3 '16 at 7:43
    
As you say, it depends on the task. By what OP said, I actually thought your first version is incorrect :P :D But really, it just isn't clear which one is the real task. – Amadan Oct 3 '16 at 7:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.