Самый известный алгоритм для нахождения всех простых чисел, не больших заданного, – решето Эратосфена. Он замечательно работает для чисел до миллиардов, может быть, до десятков миллиардов, если аккуратно написан. Однако каждый, кто любит развлекаться с простыми числами, знает, что их всегда хочется иметь под рукой как можно больше. Как-то раз мне для решения одной задачи на хакерранке понадобилась in-memory база данных простых чисел до ста миллиардов. При максимальной оптимизации по памяти, если в решете Эратосфена представлять нечетные числа битовым массивом, его размер будет около 6 гигабайт, что в память моего ноутбука не влезало. Существует модификация алгоритма, гораздо менее требовательная по памяти (делящая исходный диапазон чисел на несколько кусков и обрабатывающая по одному куску за раз) – сегментированное решето Эратосфена, но она сложнее в реализации, и результат целиком в память все равно не влезет. Ниже предлагаю вашему вниманию алгоритм почти такой же простой, как и решето Эратосфена, но дающий двукратную оптимизацию по памяти (то есть, база данных простых чисел до ста миллиардов будет занимать около 3 гигабайт, что уже должно влезать в память стандартного ноутбука).
Читать полностью »