I am attempting to implement this "find the nth prime number" algorithm in Ruby 2.1.
I've tagged it 'algorithm' as well because I think the question is language-agnostic, and that the Ruby code written is simple enough to read even if you're unfamiliar. I've used descriptive variable names to help it.
- Iterate over the whole number system, ignoring even numbers greater than 2 (2, 3, 5, 7, …)
- For each integer, p, check if p is prime:
- Iterate over the primes already found which are less than the square-root of p
- For each prime in this set, f, check to see if it is a factor of p: i. If f divides p then p is non-prime. Continue from 2 for the next p.
- If no factors are found, p is prime. Continue to 3.
- If p is not the nth prime we have found, add it to the list of primes. Continue from 2 for the next p.
- Otherwise, p is the nth prime we have found and we should return it.
Sounds simple enough. So I write my method (function):
def nth_prime(n)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
primes[-1].upto(Float::INFINITY) do |p|
return primes[n-1] if primes.length >= n-1
possible_prime = true
primes_to_check = primes.select{|x|x<=Math.sqrt(p)}
primes_to_check.each do |f|
if f%p==0
possible_prime = false
break
end
end
primes << p if possible_prime
end
end
The intent is to say nth_prime(10)
and get the 10th prime number.
To explain my logic:
I start with a list of known primes, since the algorithm requires that. I list the first ten.
Then I iterate over the entire number system. (primes[-1]+2).upto(Float::Infinity) do |p|
will offer each number up from the last known prime plus two (since +1 will result in an even number and evens over 2 cannot be prime) to infinity to the indented block as p
. I have not skipped even numbers and have
The first thing I do is return the nth prime number if the list of known primes is already at least n elements long. This works for the known values -- if you ask for the 5th, you'll get 11 as a result.
Then I set a flag, possible_prime
, to true
. This indicates that nothing has proved it to be not a prime yet. I'm going to do some tests and if it survives those without the flag being changed to false
, then p
is proven to be prime and is appended to the known-primes array. Eventually that array will be as long as n and return the nth value.
I create an array, primes_to_check
, containing all known primes <= the square root of p. Each one gets tested in turn as f
.
If f can cleanly divide p, I know that p is not prime, so I change the flag to false
, and break
, which brings us out of the primes-to-check loop and back in the upto-infinity loop. There's only one statement left in that loop, the one that appends to the known-primes array if the flag is true, which it isn't so we restart the loop with the next number.
If no f
s can cleanly divide p then p must be prime, which means it survives to the end of the primes-to-check loop with the flag still set to true, and reaches the final 'append p to known primes' statement.
Eventually this will make the primes
array sufficiently longer to answer the question "What is the nth prime?".
Problem
Asking for the 10th prime does get me 29, the last prime I pre-supplied. But asking for 11 gets nil
, or no value. I've gone over the code a hundred times and can't imagine a case in which no value gets returned.
What have I done wrong?