Решето Сундарама

[x67]

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

[yurmikh]

Приветствую Вас! По этому вопросу у меня есть следующее соображение. Иногда результат удобно хранить в виде набора данных, а иногда в виде процедуры. Все зависит от конкретных обстоятельств. Алгоритмы типа решета Эратосфена, решета Аткина, решета Сундарамма давно уже не имеют практического значения. Но это классика, и, желательно, чтобы молодые программисты имели правильные представления об их возможностях

[yurmikh]

Конечно, Вы правы! Те, кому нужно, все давно знают. Я имел ввиду следующее. Между реализациями алгоритмов просеивания простых чисел принято устраивать соревнования с заданной верхней границей интервала просеивания. Очень часто это 1 миллиард. Но в действительности, для хорошего компьютера это не так уж и много. Преимущества алгоритмов более явственно проявляются на больших интервалах. Вот я и объявил 32-битный диапазон.

[yurmikh]

Конечно, Вы правы! Те, кому нужно, все давно знают. Я имел ввиду следующее. Между реализациями алгоритмов просеивания простых чисел принято устраивать соревнования с заданной верхней границей интервала просеивания. Очень часто это 1 миллиард. Но в действительности, для хорошего компьютера это не так уж и много. Преимущества алгоритмов более явственно проявляются на больших интервалах. Вот я и объявил 32-битный диапазон.

[Matisumi]

А какой практический смысл несет в себе подобный алгоритм? Как его можно использовать в более-менее повседневных задачах, а не в академических?

[yurmikh]

Если Вы на досуге любите развлечься факторизацией, то его можно использовать при разложении на простые множители методом перебора делителей, можно, в конце концов, испытывать эстетическое удовольствие от созерцания простых чисел, ощущая при этом родственность душ с безвестным индийским студентом Сундарамом.