Самый эффективный код для первых 10000 простых чисел?

Сито Аткина , вероятно, то, что вы ищете, его верхняя граница времени выполнения составляет O(N/log log N).

Если вы только запустите числа 1 больше и 1 меньше, чем кратные 6, это может быть еще быстрее, так как все простые числа выше 3 находятся на расстоянии 1 от некоторого кратного шести. Ресурс для моего заявления

Я рекомендую использовать сито-либо сито Эратосфена , либо сито Аткина.

Сито или Эратосфен, вероятно, самый интуитивный метод нахождения списка простых чисел. В основном ты:

1. Запишите список чисел от 2 до любого предела, который вы хотите, скажем, 1000.
2. Возьмите первое число, которое не зачеркнуто (для первой итерации это 2), и вычеркните все кратные этому числу из списка.
3. Повторяйте Шаг 2, пока не дойдете до конца списка. Все числа, которые не зачеркнуты, являются простыми.

Очевидно, что существует довольно много оптимизаций, которые можно сделать, чтобы этот алгоритм работал быстрее, но это основная идея.

Сито Аткина использует аналогичный подход, но, к сожалению, я недостаточно знаю о нем, чтобы объяснить вам это. Но я знаю, что алгоритм, который я связал, занимает 8 секунд, чтобы вычислить все простые числа до 1000000000 на древнем Pentium II-350

Сито Эратосфена исходный код: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Решето Аткина исходный код: http://cr.yp.to/primegen.html

Это не совсем противоречит ограничению жесткого кодирования, но очень близко подходит. Почему бы вместо этого не загрузить этот список программно и не распечатать его?

http://primes.utm.edu/lists/small/10000.txt

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}