Paul Scott

Finding the Nth prime number

It’s a common requirement in programming challenges (such as Project Euler) to determine whether a number is a prime number. Recently I was tasked with writing a nice method of finding the nth prime number.

(Originally written in March 2010)

The obvious, brute-force 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 repeating until we find the nth. We can immediately improve this process by only considering odd numbers once we pass the number 2. Two is the only even prime: any even number is a multiple of 2 and therefore has factors besides 1 and itself.

By definition, a prime number only has factors 1 and itself and we are able to see if a number, f, is a factor of another, p, by checking f divides into p without remainder. If we then iterate from 2 to p-1, checking to see if each number is...

Continue reading →