Finding the Nth prime

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].

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(!).

StackExchange Code Review Q#90813, answer score: 4