Finding the nth Prime
It's a common requirement in programming challenges (such as Project Euler) to determine if a number is a prime number. Recently I was tasked with finding a nice method of finding the nth prime number.
The obvious solution here is to iterate through the whole number system, checking to see if each number is prime, counting how many primes we have found and then returning the nth. We can immediately improve this process by only considering odd numbers once we pass 2 (since it is the only even prime; which makes perfect sense given any even number is a multiple of 2). What we then need to do find an effective method of determining if an integer is prime.
A prime number, by definition only has factors 1 and itself and we are able to see if a number is a factor of another, p, by checking it divides into p without remainder. If we then iterate from 2 to p-1, checking to see if each number is a factor of p, we can conclude p is prime when no factors are found.
This is quite a drawn out process. The best optimisation we can include in this process is found when we consider that each factor has a reciprocal pair. For example, 6n is divided by the pairs (2, 3n) and (3, 2n). The numbers in each pair converge at the square-root of p. Immediately we can reduce the number of checks we need to make by only considering possible factors from 2 to p½.
Not knowing anything else, this is about as efficient a method we can find for determining if some integer p is prime. But in this instance we do have more information. Indeed, from counting the primes we have come across we will know the primes less than p when determining if p is itself prime.
The missing piece of the puzzle is how primes relate to lower primes. If we consider some integer n, we know what we can express n as a product of its factors. Each of those factors (integers themselves) can equally be expressed as a product of their factors, and so we can express n as the product of factors of its immediate factors. At what point does this end? When the factors are prime. Indeed, any non-prime integer can be expressed solely as the product of prime factors. Therefore, if we know all of the primes less than p and none of them divide into p without remainder, p is also prime.
And so to the solution, in which we wish to find the nth prime number:
- 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:
- 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.
A PHP implementation of this algorithm follows with a couple of further improvements. If we wish to get a set of primes, from the ith to the jth, it is extremely wasteful to continue calculating what the primes are between 1 and i (and k, for each i < k ≤ j). Thus I have implemented the ability to request an array of nth's, minimising the amount of work required. There are also a couple of optional parameters for specifying a time limit, and how accurately this limit is adhered to.