Все простые числа до 8 миллионов — примерно в 1 МБ памяти

Так работает решето Эратосфена с битовым массивом: каждому числу выделяют один бит, который показывает, вычеркнули его или ещё нет.

Начинаем с двойки и отмечаем её кратные: 4, 6, 8… Затем берём тройку: 9, 12, 15… Продолжаем для оставшихся невычеркнутых чисел.

Почему вычёркивание начинается с `i * i`? Все меньшие кратные уже обработаны. Например, для пятёрки числа 10, 15 и 20 вычеркнули на шагах двойки и тройки. Начинать можно с 25.

Для чисел меньше 8 миллионов нужно около 8 миллионов бит = 1 миллион байт. Это память для отметок; отдельный список найденных простых потребует дополнительного места.

Сами отметки делаются битовыми операциями:

- n >> 3 — индекс байта;
- n & 7 — позиция бита внутри него;
- |= — установить бит, пометив число составным.

После прохода неотмеченные числа от 2 — простые.

Алгоритму больше двух тысяч лет, а один из его полезнейших уроков всё тот же: для ответа «да или нет» достаточно одного бита.