5
\$\begingroup\$

I'm going through some of the problems over on exercism and we were asked to write a program that finds the nth prime. I know Ruby has a Prime class that handles that but the exercise doesn't allow us to use that.

My code works fine but it's very, VERY slow when testing very large numbers (e.g.: the 10,001st prime number). I'm not entirely sure of this is because of inefficient math or bad code.

  def nth(nth_prime)
    raise ArgumentError, 'Invalid Input' if nth_prime == 0

    list_of_primes = []
    results = []

    (1..2000).each do |i|
      (2..(i-1)).each do |j|
        results << i%j
      end
      list_of_primes << i unless results.include? 0
      results.clear
    end

    list_of_primes[nth_prime]
  end

Note: I've limited it to listing the primes from 2 to 2000 for now because that's fast enough for testing purposes. I've also deliberately included 1 in list_of_primes because the tests (written and provided by exercism.io) test that asking for the 1st prime will give you the number 2 so I needed 2 to be at list_of_primes[1].

\$\endgroup\$
  • 2
    \$\begingroup\$ There are literally hundreds of questions about finding prime numbers on this site. A little searching will show you many tips to improve your speed. \$\endgroup\$ – Emily L. May 15 '15 at 11:02
  • \$\begingroup\$ @EmilyL I've looked through some - a lot are written in python/c and I'm just having a little trouble parsing most of them since I don't know the languages. I did read about the Sieve of Erasthenes though and I'll try to implement that in ruby. \$\endgroup\$ – SoSimple May 15 '15 at 11:24
3
\$\begingroup\$

First let's take a second to think about your current approach.

  • For each time the outermost loop iterates you loop n-2 times over the inner loop.
  • For each time the inner loop iterates you loop over each item in results. (include? is most likely doing at least some kind of looping under the hood. How efficient the algorithm is I don't know.)

So, the first obvious optimization to make is to special case the number 2 as it's the only even prime number. Add it directly to your final list_of_primes from the get go. Then you only have to check every other number in your inner loop. In other words, increment by two instead of one.

(3..(i - 1)).step(2) do |j|

The second thing to do is to get rid of the intermediate results (and thus another, albeit implicit loop). You can do this by checking each i To see if it's prime. A naive approach is to check its modulus against each number less than j and break from the inner loop if it's equal to zero.

  if (i % j == 0) then
    isPrime = false
    break
  end
end

list_of_primes >> i if isPrime

Now, I say this is naive only because we don't have to check each number up to j. We only need to loop up to the square root of j. If j isn't divisible by a number less than or equal to its square root. It's prime. Go ahead. Go check. I'll wait.

...

Pretty cool, eh? So, your inner loop would end up looking something like this.

    (3..(Math.sqrt(i))).step(2) do |j|

Anyway, there are other completely different algorithms for this. Typically, when searching for all the prime numbers up to n, we'd use the Sieve of Eratosthenes.

Lastly, I apologize if my syntax is wrong or the code isn't very idiomatic. It's been a long time since I wrote any Ruby and I never was very good at it. Hopefully this still helps.

\$\endgroup\$
  • \$\begingroup\$ Thanks so much for this! I know my logic was highly inefficient but math has never been my strong suit and I couldn't figure out another way to go about this problem. You've at least go me thinking in a more effective manner - which is what I really needed, and I'll try and implement some of your suggestions and this Sieve method. Thanks again! \$\endgroup\$ – SoSimple May 15 '15 at 12:06
  • \$\begingroup\$ You're welcome! Just note that the sieve is an entirely different way to go about this and my suggestions above might not help you with that approach. Good luck! \$\endgroup\$ – RubberDuck May 15 '15 at 12:08
4
\$\begingroup\$

Using @RubberDuck's reference to the Sieve of Eratosthenes, I came up with the following code for listing prime numbers:

def list_primes up_to
  primes = (2..up_to).to_a
  primes.each {|num| primes.delete_if {|i| i > num && (i % num) == 0} }
  primes
end

The code is fairly simple. We build an array of all the numbers up to up_to and start deleting from that list every number that is devisable by any of it's predecessors (not a prime).

This promises less iteration, since we don't have to review numbers more than once and all the predecessors we check against are prime numbers, so we don't have to check against numbers that are irrelevant (i.e. checking against 6 when we already checked agains 2 and against 3).

Benchmarking this code in comparison to your code showed that listing the prime numbers up to 10,000 took 0.09 seconds using this application for the Sieve of Eratosthenes vs. 3.65 seconds using your code... That's about 40 times faster(!)*.

I would say, although my code might not be the best way to write the Sieve of Eratosthenes in Ruby, that @RubberDuck's advice is pure gold.

Reading about it in Wikipedia, it seems that n * log(n) would offer a number close to the prime number... so this will help up determine up to what number we should search....

Here's my version of the code, which assumes the first prime number to be 2:

def my_nth_prime n
  up_to = n * (Math.log(n) + 2)
  primes = (2..up_to).to_a
  primes.each {|num| primes.delete_if {|i| i > num && (i % num) == 0} }
  primes[n-1]
end

up_to will designate the upper limit for the prime numbers (prime numbers up to that number will be calculated). It is calculated using the rule of n * log(n) suggested by Wikipedia...

...BUT, that rule might brake down, as it's only an approximation. So, just to be on the safe side, we add another 2 ns to the up_to, making sure we don't get caught by a lower approximation than the actual nth prime.

Once these two things are done, we build an array of all the primes up to up_to and select the n-1 prime (arrays are 0 based, meaning the first item is at [0] so the nth prime is actually [n-1]).

To build the array we use the same code as before, collecting all the numbers up to up_to and deleting any number that is devisable by any of it's predecessors (leaving the predecessors to be only prime numbers, this saves us a lot of testing and iterations).

Good Luck!


  • although the Ruby code I provided might be faster, it's extremely slow compared to the Prime core class... Getting the 10,000th prime using my code took my computer 7.52 seconds, vs. 0.002925 seconds using the native module(!).
\$\endgroup\$
0
\$\begingroup\$

Why are you making a list of primes. They will hold up a lot of memory. Instead make a variable to hold prime number and another variable to count which number is this prime. Like,

count  = 1
Prime = 2 #Keep increasing this number and if it is prime increase the count variable up till you reach the count
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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