Недавно, когда пришлось находить простые числа на Python, решил немного математики в это добавить. Находя списки простых чисел на некотором интервале, так называемое "просеивание", понял, что обычным способом стандартное решето Эратосфена применять нельзя: оно подходит лишь для первых чисел. То есть можно с его помощью найти, скажем все простые 2 до 1000000000, или от 2 до 2000000000, но чтобы найти с помощью решета простые от 1000000000 до 2000000000, надо найти все простые от 2 до 2000000000 и потом откинуть те, что меньше 1000000000. И вычислительная сложность с углублением вдаль натурального ряда растёт не оправдано стремительно.
Подумал, как бы сам процесс просеивания Эратосфена расширить для произвольных натуральных интервалов и натолкнулся на
описание метода индийского математика Сандарама. В приведенной статье метод доходчиво объясняется, приводить его не буду.
В общем, остаётся написать код. Используем numpy и получаем действительно быстрые расчеты на числах порядка 10^18.
Использовался Python 2.7.
Зачем именно человеку такое может понадобится? Об этом, вероятно, расскажу в следующих статьях.
