Каково будет 10001-ое простое число? На языке С#

Аксиоматика:
- Число n > 1 является простым, если делится нацело только на единицу и на n;
- Число a делится нацело на b, если остаток от деления a на b равен нулю;
- От пеcтановки мест множителей произведение не меняется;
- Составным называется число, которое не является простым;

Следствие из первой и второй аксиом: для того, чтобы определить, является ли число n простым, необходимо для каждого 1 < i < n проверить остаток от деления n на i на рвенство нулю.
Следствие из первой, второй и третьей аксиом: если число n может быть представлено как произведение двух чисел a и b и a <= b, то для проверки n на простоту достаточно проверить на равенство нулю остаток от деления n на a.
Следствие из первой и четвёртой аксиом: если число n может быть разложено на множители, один или несколько из которых являются составными, то каждый из составных множителей также может быть разложен на множители и так до тех пор, пока среди всех множителей не окажутся лишь простые числа.
Из всего этого следует, что для проверки числа n на простоту достаточно проверить остаток от деления n на все простые числа i < n, для которых i <= n / i. Последнее условие получено из цепочки
n = a * b
b = n / a

a <= b
a <= n / a или !(n / a < a)

Данный подход позволит существенно понизить сложность алгоритма проверки на простоту (то есть, уменьшить количество итераций) за счёт хранения в памяти простых чисел, уже прошедших проверку.

Реализуем этот принцип.

using System;
using System.Collections.Generic;

/// <summary>
/// Функция проверки на простоту
/// </summary>
static bool IsPrime(int n, IEnumerable<int> primes)
{
if (n < 2)
return false;

foreach (int prime in primes)
{
if (n / prime < prime)
return true;

if (n % prime == 0)
return false;
}

return true;
}

Полагаем, что в объекте перечислимого типа primes хранятся все простые числа i, упорядоченные по возрастанию, где 2 <= i < n.

Далее, опишем функцию нахождения простого числа с индексом index, полагая, что индексация ведётся с нуля (то есть, для index = 0 функция вернёт 2). Для хранения найденных простых чисел будем использовать Queue< T > из System.Collections.Generic в качестве списка с возможностью добавления элемента в конец.

static int GetPrime(int index)
{
Queue<int> primes = new Queue<int>();

int found_count = 0;
for (int i = 2; ; i++)
{
if (IsPrime(i, primes))
{
if (index == found_count)
return i;
else
{
primes.Enqueue(i);
found_count++;
}
}
}
}

Ну, и Main():

static void Main()
{
// Инедксация ведётся с нуля, так что
// от порядкового номера отнимаем единичку.
const int index = 10001 - 1;

int result = GetPrime(index);

Console.WriteLine(result);
Console.ReadKey();
}

Ответ - 104743.