Find the 10001st prime

Question

I took a look at the following question from project euler:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?

I tried to take the square root of the number and than find all the prime numbers below the square root of the number and then divide the number by all the square roots and see if there is 0 left each time. If the number is not divisible by all the primes under its square root its a prime number. I did this to lower the itterations the programm has to make. Here is what I have now, I am not sure why it isn't working. Anybody knows what i did wrong?

  List<int> primeNumbers = new List<int>();
        bool prime = true;
        bool MainPrime = true;
        int check = 1;
        for (long i = 3; i < long.MaxValue; i++)
        {
            if ((i % 2) != 0)
            {
                int root = Convert.ToInt32(Math.Sqrt(i));
                for (int j = 1; j < root; j++)
                {
                    for (int k = 2; k < j; k++)
                    {
                        if ((j% k) == 0)
                        {
                            prime = false;
                        }
                    }
                    if (prime)
                    {
                        primeNumbers.Add(j);
                    }
                    prime = true;
                }

            }
            foreach (var item in primeNumbers)
            {
                if ((i%item) == 0)
                {
                    MainPrime = false;
                }
            }
            primeNumbers.Clear();
            if (MainPrime)
            {
                check++;
            }
            if (check == 10001)
            {
                Console.WriteLine(i);
                break;

            }
        }

        Console.ReadKey();

Answer 1

Several points:

1. When finding possible prime divisors, you need to check all numbers up to the square root included, so your condition j < root is incorrect.

2. You don't have to recalculate the primes again for every number. Keep the list as you go and add new primes to it.

3. As soon as you find a divisor, you can break out of the foreach loop.

Improved code:

List<long> primeNumbers = new List<long>() { 2 };
for (long i = 3; i < long.MaxValue; i += 2)
{
    if(!primeNumbers.Any(p => (i % p) == 0))
    {
        primeNumbers.Add(i);
        if (primeNumbers.Count == 10001)
        {
            Console.WriteLine(i);
            break;
        }
    }
}

Gives 104743 as the 10001st prime.