Finding the Nth prime

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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