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 n
s to the up_to
, making sure we don't get caught by a lower approximation than the actual n
th 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 n
th 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(!).