EDIT_ADD: Если Уилл Несс прав, что целью вопроса является просто вывод непрерывного потока простых чисел в течение всего времени работы программы (нажатие кнопки «Пауза / Разрыв» для паузы и любая клавиша для повторного запуска) ) без какой-либо серьезной надежды на каждое достижение этого верхнего предела, тогда код должен быть написан без аргумента верхнего предела и проверки диапазона «true» для первого цикла «i» for. С другой стороны, если вопрос хотел на самом деле вывести простые числа до предела, то следующий код сделает работу намного эффективнее, используя пробное деление только для нечетных чисел, с тем преимуществом, что он вообще не использует память (это также может быть преобразовано в непрерывный цикл согласно приведенному выше):
static void primesttt(ulong top_number) {
Console.WriteLine("Prime: 2");
for (var i = 3UL; i <= top_number; i += 2) {
var isPrime = true;
for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) Console.WriteLine("Prime: {0} ", i);
}
}
Во-первых, код вопроса не производит вывод, потому что его переменные цикла являются целыми числами, а проверяемый лимит является огромным длинным целым числом, что означает, что цикл не может достичь предела, создавая внутренний цикл EDITED: в результате чего переменная 'j' возвращается к отрицательным числам; когда переменная 'j' возвращается к -1, проверяемое число не проходит простое тестирование, поскольку все числа делятся на -1 END_EDIT . Даже если бы это было исправлено, код вопроса производит очень медленный вывод, потому что он связан с выполнением 64-битного деления очень больших количеств составных чисел (все четные числа плюс нечетные составные) на весь диапазон чисел до этой вершины число десять возведено в шестнадцатую степень для каждого простого числа, которое оно может произвести. Приведенный выше код работает, потому что он ограничивает вычисление только нечетными числами и выполняет только деление по модулю до квадратного корня текущего проверяемого числа .
Требуется час или около того, чтобы отобразить простые числа до миллиарда, поэтому можно представить, сколько времени потребуется, чтобы показать все простые числа до десяти тысяч триллионов (от 10 до шестнадцатой степени), особенно когда расчет становится медленнее с увеличением диапазона. END_EDIT_ADD
Несмотря на то, что ответ одного типа (вроде) @SLaks с использованием Linq работает, на самом деле это не «Сито Эратосфена», а просто неоптимизированная версия Trial Division , неоптимизированная в этом смысле. не удаляет нечетные простые числа, не начинается с квадрата найденного базового простого числа и не прекращает отбраковку базовых простых чисел, больших чем квадратный корень из верхнего числа для просеивания. Это также довольно медленно из-за множественных вложенных операций перечисления.
На самом деле это злоупотребление методом Linq Aggregate, и он не использует эффективно первый из двух сгенерированных диапазонов Linq. Он может стать оптимизированным пробным отделом с меньшими накладными расходами перечисления следующим образом:
static IEnumerable<int> primes(uint top_number) {
var cullbf = Enumerable.Range(2, (int)top_number).ToList();
for (int i = 0; i < cullbf.Count; i++) {
var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
} return cullbf; }
, который работает во много раз быстрее, чем ответ SLaks. Тем не менее, он все еще медленный и занимает много памяти из-за генерации списка и нескольких перечислений, а также операций множественного деления (подразумеваемых по модулю).
Следующая истинная реализация Sieve of Eratosthenes работает примерно в 30 раз быстрее и занимает гораздо меньше памяти, так как использует только одноразрядное представление для каждого просеянного числа и ограничивает его перечисление до конечной выходной последовательности итератора, а также оптимизирует только обработку нечетные композиты и отбраковка только от квадратов базовых простых чисел для базовых простых чисел до квадратного корня из максимального числа, как показано ниже:
static IEnumerable<uint> primes(uint top_number) {
if (top_number < 2u) yield break;
yield return 2u; if (top_number < 3u) yield break;
var BFLMT = (top_number - 3u) / 2u;
var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
var buf = new BitArray((int)BFLMT + 1,true);
for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
var p = 3u + i + i; if (i <= SQRTLMT) {
for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
buf[(int)j] = false; } yield return p; } }
Приведенный выше код вычисляет все простые числа до десяти миллионов в диапазоне около 77 миллисекунд на Intel i7-2700K (3,5 ГГц).
Любой из двух статических методов может быть вызван и протестирован с помощью операторов using и статического метода Main следующим образом:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
static void Main(string[] args) {
Console.WriteLine("This program generates prime sequences.\r\n");
var n = 10000000u;
var elpsd = -DateTime.Now.Ticks;
var count = 0; var lastp = 0u;
foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }
elpsd += DateTime.Now.Ticks;
Console.WriteLine(
"{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
count, n, lastp,elpsd / 10000);
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
, который покажет число простых чисел в последовательности до предела, последнее найденное простое число и время, затраченное на перечисление этого количества.
EDIT_ADD: Однако, чтобы получить перечисление числа простых чисел менее десяти тысяч триллионов (от десяти до шестнадцатой степени), как задает вопрос, сегментированный постраничный подход с использованием многоядерной обработки требуется, но даже с C ++ и очень высокооптимизированным PrimeSieve , для получения числа найденных простых чисел потребуется более 400 часов, а для перечисления всех их в десятки раз больше, чем за год делать то, что задает вопрос. Чтобы сделать это с использованием неоптимизированного алгоритма Trial Division, понадобятся супер-эоны и очень-очень долгое время даже при использовании оптимизированного алгоритма Trial Division, как, например, от десяти до двух миллионных энергетических лет (это два миллиона нулей! !).
Неудивительно, что его настольный компьютер просто сидел и зависал, когда он пытался это сделать !!!! Если бы он попробовал меньший диапазон, например, миллион, он все равно обнаружил бы, что это занимает в секундах, как реализовано.
Решения, которые я выкладываю здесь, тоже не сработают, так как даже последнему Сите Эратосфена потребуется около 640 Терабайт памяти для этого диапазона.
Вот почему только сегментированный на странице подход, такой как PrimeSieve, может решить такую проблему для заданного диапазона, и даже это требует очень длительного времени, например, от нескольких недель до нескольких лет, если только у человека нет доступа к супер компьютер с сотнями тысяч ядер. END_EDIT_ADD