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

Сегодня я хотел бы поделиться с вами различными вариантами реализации поиска простых чисел на языке C#, начиная с классических алгоритмов — решета Эратосфена, Сундарама и Аткина, и кончая различными оптимизациями (сегментация, факторизация). Особый упор я делал на простоту: самый быстрый из алгоритмов, который мне удалось получить, содержит 120 строк кода и ищет простые числа до триллиона меньше, чем за 30 минут, а до миллиарда — меньше, чем за секунду (это далеко от производительности лучших из существующих библиотек по поиску простых чисел, но эти библиотеки обычно содержат свыше 4000 строк кода).
В заключение мы применим самую быструю реализацию для поиска максимального расстояния между двумя соседними простыми числами до триллиона. Прежде чем заходить под кат, я предлагаю вам попытаться угадать ответ. Для сравнения, для простых чисел до 100 максимальное растояние равно 8 (между соседними простыми числами 89 и 97), а до тысячи — 20 (между 887 и 907).

Весь исходный код можно найти на гитхабе.

Битборды (Bitboard) — специальные битовые структуры, позволяющие эффективно рассчитывать ходы в настольных играх. На хабре писали про применение битбордов к шахматам и даже к шашкам. Сегодня мы применим технику битбордов к несколько неожиданной, но всем знакомой игре – к тетрису. Результатом наших изысканий будет консольная игра, а также автоматический поиск лучших ходов (при заданной последовательности фигур), скорость которого как раз и обеспечивается эффектиностью битовых манипуляций. Заодно мы поддержим проигрывание найденных ходов в автоматическом режиме, чтобы в полной мере насладиться компьютерным интеллектом. В конце статьи дана ссылка на гитхаб с кодом игры на C#, а также коротенькое видео игры из 114 ходов, найденной компьютером поиском в глубину за пятнадцать минут.

Обычно битборд – это машинное слово, состоящее из нескольких байт, каждый бит которого соответствует одной клетке поля в игре. Так, в шахматах всего 64 клетки, что соответствует 8-байтному слову (ulong в C#), а в шашках – 32 (uint в C#). Любители тетриса наверняка помнят, что размер поля в стандартном тетрисе – 10 на 20 клеток, то есть, 200 бит, что не влезает ни в один числовой тип. Конечно, можно разбить поле на четыре части и использовать четыре восьмибайтных слова, или можно не мелочиться и использовать массив из двадцати двухбайтных слов, по одному слову на каждую линию поля; все реализации тетриса на битбордах, которые я нашел (в количестве одной штуки), так и делают. Но мы пойдем другим путем…

Сложно найти человека, не знакомого с игрой "Жизнь", придуманной английским математиком Джоном Конвеем еще в 1970 году, и до сих пор не теряющей своей популярности. Многие программисты писали свою реализацию этой игры, и еще одна вряд ли кого-то удивит. Однако эта игра является отличным примером, показывающим, насколько полезной может оказаться оптимизация вычислений, даже не меняющая асимтотическую сложность алгоритма. Мы начнем с простейшей реализации на c# и будем последовательно применять различные оптимизации, ускоряя работу программы.

Мы также улучшим алгоритм на JavaScript, ускорив его в 10 раз по сравнению с неоптимизированной версией.

В конце статьи дана ссылка на код, а также на online-реализацию игры с оптимизированным алгоритмом на JavaScript, выполняющим до двухсот итераций в секунду на поле размера 1920x1080 (Full HD), где вы можете убить время поиграть в эту замечательную игру.

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