07: 10001st prime

Problem statement

By listing the first six prime numbers: 2, 3, 5, 6, 11, and 13, we can see that the 6th prime is 13.

What is thes 10 001st prime number?

Thoughts

Given that there is no formula for determining the nth prime number, this will have to be computed recursively (or iteratively).

Solution

Define an array to store our primes and the limit we want to search to For every number from 3 upwards, check if it's divisible by any of the primes so far. If not, then it must be prime. If we determine it's not prime, break out of the loop straight away. If we determine it is prime, add it to the list.

const int limit = 10001;
#include <stdbool.h>
#include <stdio.h>
int main()
{
	int primes[limit];
	primes[0] = 2;
	int currentIdx = 1;

	int num = 3;
	while (currentIdx < limit) {
		bool isPrime = true;
		for (int i = 0; i < currentIdx; i++) {
			int prime = primes[i];
			if (num % prime == 0) {
				isPrime = false;
				break;
			}
		}

		if (isPrime) {
			primes[currentIdx++] = num;
		}
		num++;
	}
	printf("%d", primes[limit - 1]);
}

I'm sure there are much better, faster ways of doing this, if you cared to put the time in. This is fairly simple and gets the job done.