Несмотря на простоту (и, в общем-то, тривиальность, если подумать) описываемого решения, наткнулся на него чисто случайно, во время разукрашивания комментарием законченной программы, готовой к сдаче.

В программистской практике регулярно случается ситуация, когда на время разработки и отладки требуется включать какой-то код и выключать другой. Это несложно делать специальными конструкциями типа #if true ... #else ... #endif, меняя true на false, или прибегая к более изощренным условиям.

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

 

Так, формат 16-разрядных беззнаковых целых при размере такой таблицы около 13 килобайт вмещает всего лишь 6542 простых числа: вслед за числом 65531 идут значения более высокой разрядности. Такая таблица годится разве что в качестве игрушки.

 

Наиболее ходовой в программировании формат 32-разрядных целых выглядит значительно солиднее — он позволяет хранить около 203 млн простых. Но такая таблица занимает уже около 775 мегабайт.

 

Еще больше перспектив у 64-разрядного формата. Однако при теоретической мощности порядка 1e+19 значений, таблица имела бы размер 64 экзабайта.