Библиотека School: быстрая работа с простыми числами

Если вам приходилось обращаться к библиотеке School при большом объеме работы с простыми числами, вы могли заметить, что эта работа происходит весьма быстро во всем диапазоне натуральных чисел, представимых типом integer. В чем тут секрет?

Немного теории

В диапазоне от 2 до 2 147 483 647 содержится 105 097 565 простых чисел. На выяснение этого факта мой компьютер потратил 13,2 с (с учетом того, что был получен список всех этих 105 миллионов чисел). Понятно, что никакое обычное "решето" не сможет просеять два с лишним миллиарда чисел по той простой причине, что в программе не получится объявить массив подобного размера. Поэтому приходится использовать алгоритм "Модифицированное решето Эратосфена". Его суть в том, что весь диапазон чисел разбивается на поддиапазоны (сегменты) и каждом из них используются простые числа, полученные в предшествующем диапазоне. Конечно, это несколько увеличивает время работы.

Алгоритм проверки числа на простоту предусматривает перебор его возможных делителей. Понятно, что проверив делимость на 2, далее нужно проверять только нечетные делители. И понятно, что проверять нужно делители, квадрат которых не превышает самого числа. Это означает, что делители числа типа integer не могут превышать квадратного корня из числа 2 147 483 647, т.е. значения 46 340. А этому интервалу принадлежат всего-то 4 704 простых числа. Так почему бы не потратить смехотворное время и заранее не просеять эти 46340 чисел, получив массив простых чисел размером 4 704 элемента?

Но... ох уж это маленькое "но"! Квадрат числа 46340 равен 2 147 395 600 и числа из диапазона [2 147 395 601; 2 147 483 647] из проверки выпадают. А там находятся еще 4 085 простых чисел! Посему придется увеличить 46 340 на единицу и смириться с тем, что квадрат 46 341 требует для размещения тип int64.

И тут мы обнаруживаем, что модифицированное решето Эратосфена требует, чтобы длина сегмента была простым числом. А ближайшее простое, большее или равное 46 341 - это 46 349. Вот таков окончательный размер решета.

Реализация

Если заглянуть в исходный код библиотеки School, можно обнаружить три "магические" переменные и список LPrimes.

LPrimes: List<integer>; // на отрезке [2;46348]
ubPrimeDivs := 46349;
nPrimeDivs: integer; // 4792
MaxPrimeDiv: integer; // 46349

Вы уже увидели в этой "магии" то самое значение 46 349? Но что такое 4 792? А это количество простых чисел на интервале длиной 46 349, т.е. [0; 46 348] и там их ровно 4 792.

При запуске программы, использующей библиотеку School, всегда "на всякий случай" заполняется список LPrimes, содержащий 4792 первых простых числа - делителей из нулевого сегмента "решета". Это всего-то менее 20К памяти, а процесс увеличивает время запуска на совершенно смехотворную величину.

Что это даёт

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