Быстро и компактно первые миллиарды простых чисел

[rockclimber]

Ende
Выделено из темы «Аддитивная теория простых чисел»

mathpath в сообщении #1716645 писал(а):

А сегодня я попросил дипсик реализовать этот алгоритм на расте для диапазона в один миллиард, и он написал программу за час.
Ну как за час: он выдает версию, я ее компилирую, вижу, что есть ошибки, я ему говорю - чувак, вот эта строка падает вот с такой ошибкой, он ее тут же исправляет, и так за пару часов мы управились.
Я в коде вообще ни строчки не написал.

Увидел топик только сегодня и не смог пройти мимо.
Так совпало, что неделю назад я начал изучать rust и тоже начал с написания решета эратосфена. И тоже управился часа за два-три - но почти без помощи ИИ (только пару раз задал пару небольших вопросов по поводу ошибок). Так что кажется, такой ИИ бесполезен. Кстати, ради прикола переписал код с rust на freepascal, спросил у чатгпт, с какими ключами запускать компиляторы обоих языков для максимальной оптимизации, и что же вы думаете? Обе программы работают за одинаковое время. Проверял на поиске простых чисел до миллиарда.

Что еще может пригодиться.
Если у вас линукс, то время выполнения и потребление памяти можно анализировать линуксовыми утилитами, то есть код для измерения времени писать не надо. Мелочь, а приятно. Делается так:

/usr/bin/time -v /path/to/your/program >/dev/null

Cократить потребление памяти можно, если упаковать данные следующим образом: создать массив 64-битных чисел, каждый бит кодирует одно нечетное число. Первый бит означает 1, второй - 3, третий - 5, и т. д.
Значения битов: 0 - простое, 1 - составное. Или наоборот, если вам так удобнее.

В таком виде, для поиска всех чисел до миллиарда вам нужно около 15 МБ памяти (а не гигабайт). Но резко вырастает нагрузка на мозг, отладка займет на порядок больше времени, и ИИ может не справиться.

[Dmitriy40]

rockclimber в сообщении #1718046 писал(а):

Cократить потребление памяти можно, если упаковать данные следующим образом: создать массив 64-битных чисел, каждый бит кодирует одно нечетное число. Первый бит означает 1, второй - 3, третий - 5, и т. д.
Значения битов: 0 - простое, 1 - составное. Или наоборот, если вам так удобнее.

Можно и ещё упаковать: в каждом байте хранить биты простоты 8-ми чисел из 30, а именно [+1,+7,+11,+13,+17,+19,+23,+29]. Простые 2,3,5 обрабатывать отдельно. Для чисел до миллиарда понадобится 1e9/30=32МБ.
Запускать на таком массиве решето Эратосфена ещё сложнее, да. Хотя можно внаглую запустить их 8шт (последовательно) для каждого бита в байте, тогда они все одинаковые и обычные.

rockclimber в сообщении #1718046 писал(а):

В таком виде, для поиска всех чисел до миллиарда вам нужно около 15 МБ памяти (а не гигабайт).

Ошиблись, 1e9/2/8=59.6МБ, не 15МБ.

rockclimber в сообщении #1718046 писал(а):

Обе программы работают за одинаковое время. Проверял на поиске простых чисел до миллиарда.

Учитывая что это порядка нескольких секунд (а то и меньше секунды), лучше было бы проверять скорость до 10млрд и несколько раз, на малых интервалах большая погрешность.

[rockclimber]

Dmitriy40 в сообщении #1718060 писал(а):

Можно и ещё упаковать: в каждом байте хранить биты простоты 8-ми чисел из 30, а именно [+1,+7,+11,+13,+17,+19,+23,+29]. Простые 2,3,5 обрабатывать отдельно.

А можете эту мысль подробнее развернуть? Это какая-то вариация решета Причарда? Что-то слишком сложно выглядит...

Dmitriy40 в сообщении #1718060 писал(а):

Ошиблись, 1e9/2/8=59.6МБ, не 15МБ.

Да, точно, не на ту строчку в отчете посмотрел (точнее, не ту строчку запомнил ).

Dmitriy40 в сообщении #1718060 писал(а):

Учитывая что это порядка нескольких секунд (а то и меньше секунды)

У меня это занимает 10 секунд. Это без "битового сжатия". Сейчас пишу более оптимизированную версию, с сжатием, но написание идет не быстро - приходится параллельно язык учить .

-- 11.02.2026, 12:19 --

UPD

Dmitriy40 в сообщении #1718060 писал(а):

Можно и ещё упаковать: в каждом байте хранить биты простоты 8-ми чисел из 30, а именно [+1,+7,+11,+13,+17,+19,+23,+29].

Идея в общем-то понятная, но как с этим дальше работать? Сложновато будет, нет?

[Dmitriy40]

rockclimber в сообщении #1718062 писал(а):

А можете эту мысль подробнее развернуть? Это какая-то вариация решета Причарда?

Возможно и Причарда, не уверен.
Просто наблюдение: среди 6 чисел подряд начиная с любого кратного 6 простыми могут оказаться лишь 2 (+1,+5), а среди 30 чисел подряд начиная с любого кратного 30 простыми могут быть лишь указанные 8 штук (кроме первых 5 натуральных, их обработать отдельно, ровно как и простое 2 для варианта с только нечётными). Это тривиально доказывается проверкой делимости остальных на 2,3,5. Повезло что их ровно 8 штук - укладываются точно в байт. Значит каждый байт может содержать флаги простоты всех 30 чисел начиная с любого кратного 30. Т.е. коэффициент сжатия 30/8=3.75.
Почти как с нечётными, только не по модулю 2, а по модулю 30.
По модулю 6 тоже можно, но нужно хранить пары битов для каждых 6 натуральных чисел, т.е. коэффициент сжатия 6/2=3 вместо 2/1=2 для только нечётных. Но с парами битов работать неудобно.
Можно и ещё больше модуль взять, например 7#=210, тогда вместо 8*7=56 чисел простыми могут быть лишь 48, остальные будут кратными 7. Но 48 бит неудобно хранить. А выигрыш в размере всего лишь 4.375 вместо 3.75.
Можно и ещё больше модуль взять, хоть 11# или 13# или 17# или 19# или 23#, но с каждым увеличением выигрыш падает, хотя для 23# коэффициент сжатия составляет уже $\prod\limits_{p\in P}^{23}\dfrac{p}{p-1}=6.113$. Но ещё ведь и надо вычислить все эти возможные простые по модулю 23#=223млн ... А по модулю 30 легко всё проверить в уме.

С модулями больше 2 будут проблемы с самим решетом так как числа идут с переменным шагом (в отличие от модуля 2, когда все нечётные кандидаты в простые равномерны) и переход от текущего числа к следующему должен учитывать что не все числа представлены в виде битов и такие числа пропускать снова добавляя простое. Но повторюсь это можно решить втупую, ведь каждый отдельный вариант из 8-ми (для модуля 30) распределён снова равномерно (например +7, +37, +67, +97, +127, ...) и потому для каждого из них в отдельности можно смело запускать решето в обычном варианте, по отдельным битам в байте.

По поводу ускорения, почитайте про сегментированное решето, оптимизированное под размер кэша процессора, это очень существенно ускоряет работу с массивом. Ну и от умножений и делений можно отказаться, обойтись только сложениями/вычитаниями.

Для ориентирования, одна из самых быстрых программ primesieve, подсчитывает количество простых до миллиарда за 0.15с-0.2с и за 2с до 10млрд. Я так не умею, у меня получается лишь втрое медленнее.

[rockclimber]

Dmitriy40 в сообщении #1718070 писал(а):

rockclimber в сообщении #1718062 писал(а):

А можете эту мысль подробнее развернуть? Это какая-то вариация решета Причарда?

Возможно и Причарда, не уверен.
Просто наблюдение: среди 6 чисел подряд начиная с любого кратного 6 простыми могут оказаться лишь 2 (+1,+5), а среди 30 чисел подряд начиная с любого кратного 30 простыми могут быть лишь указанные 8 штук (кроме первых 5 натуральных, их обработать отдельно, ровно как и простое 2 для варианта с только нечётными). Это тривиально доказывается проверкой делимости остальных на 2,3,5. Повезло что их ровно 8 штук - укладываются точно в байт. Значит каждый байт может содержать флаги простоты всех 30 чисел начиная с любого кратного 30. Т.е. коэффициент сжатия 30/8=3.75.
Почти как с нечётными, только не по модулю 2, а по модулю 30.
По модулю 6 тоже можно, но нужно хранить пары битов для каждых 6 натуральных чисел, т.е. коэффициент сжатия 6/2=3 вместо 2/1=2 для только нечётных. Но с парами битов работать неудобно.
Можно и ещё больше модуль взять, например 7#=210, тогда вместо 8*7=56 чисел простыми могут быть лишь 48, остальные будут кратными 7. Но 48 бит неудобно хранить. А выигрыш в размере всего лишь 4.375 вместо 3.75.

Ну да, решето Причарда примерно так и работает. Я целый день убил на прошлой неделе, чтобы в нем разобраться, и в итоге пришел к выводу, что не очень-то оно мне и нужно. Там строится "колесо" из чисел, которое как бы "прокатывается" по числовой оси и отмечает простые числа. Потом на основе результата строится следующее колесо, и так далее. Первое колесо имеет размер 2 и состоит из числа 1, второе колесо - длины 6 и числа 1 и 5, третье - длины 30 и практически ваши 1, 5, 7, 11, 13, 17, 19, 23, 25, 29. Каждое новое колесо "открывает" новое простое число, а длина колеса - это примориал последнего найденного числа.

Dmitriy40 в сообщении #1718070 писал(а):

Ну и от умножений и делений можно отказаться, обойтись только сложениями/вычитаниями.

А у меня вообще почти нет всех четырех операций - только несколько вспомогательных. Так как у меня закодированы нечетные числа, я применяю следующий алгоритм: беру битовый массив, где одни нули. Единицами помечаю составные числа. Сначала у меня есть одно простое - $3$. Делаю маску - три байта:
10010010
00100100
01001001
Последовательно применяю эту маску к массиву чисел. Первый байт маски к первому числу, второй - ко второму, третий - к третьему, потом опять первый байт маски - к четвертому и так до конца по кругу. "Применение маски" - это логическое или:

numbers[i] = numbers[i] | mask[j]

А так как у меня (как и у всех в общем) 64-битный процессор, то я использую 64-битные числа и маски. И одно применение маски позволяет мне пометить сразу несколько десятков чисел, кратных трем. Количество чисел в маске равно проверяемому простому. Для простых, которые больше 64, некоторые числа в маске - нули, их можно не применять (потому что они ничего не меняют), поэтому я сделал два массива - один хранит маски, второй - смещения.

Этот код я только-только дописал, буквально пару часов назад, там еще куча багов пока, и правильный результат он не дает
Но работает быстро - в этом "масочном" режиме я проверяю числа до миллиарда уже за 2,5 секунды против 10 секунд у простого решета.
Следующий этап оптимизации, который я планировал попробовать - это делать составные маски для нескольких простых чисел сразу. Например, если сделать маску размером 105 чисел ($3 \cdot 5 \cdot 7$), то можно вместо 3 проходов для каждого простого сделать один. А плата небольшая - всего 100 байт оперативной памяти.

Dmitriy40 в сообщении #1718070 писал(а):

По поводу ускорения, почитайте про сегментированное решето, оптимизированное под размер кэша процессора, это очень существенно ускоряет работу с массивом.

Я уже немного в курсе теории, но практического опыта такой оптимизации пока нет. Чатгпт рекомендует ориентироваться на размер кэша L2, но, как я понимаю, невозможно явно указать процессору "держи этот массив в кэше". Процессор сам решает. Я планировал попробовать делать маски для своего алгоритма (выше описал) как раз такими, чтобы в L2 влезали (то есть сначала общая маска для чисел 3, 5, 7, 11, 13, 17, 19, потом для 23, 29, 31, 37, 41, потом 43, 47, 53, 59, 61, и так далее). Опять же, чатгпт говорит, идея ок, процессор будет держать эти маски в кеше. Дальше пока мои планы не идут.

Dmitriy40 в сообщении #1718070 писал(а):

Для ориентирования, одна из самых быстрых программ primesieve, подсчитывает количество простых до миллиарда за 0.15с-0.2с и за 2с до 10млрд. Я так не умею, у меня получается лишь втрое медленнее.

Ну вот, а моя всего лишь в 10 раз отстает, еще чуть-чуть поднажму, и получу заслуженное третье место

[Dmitriy40]

rockclimber в сообщении #1718080 писал(а):

Я планировал попробовать делать маски для своего алгоритма (выше описал) как раз такими, чтобы в L2 влезали (то есть сначала общая маска для чисел 3, 5, 7, 11, 13, 17, 19, потом для 23, 29, 31, 37, 41, потом 43, 47, 53, 59, 61, и так далее).

Это не лучший вариант: запись в память тормозит гораздо сильнее чтения памяти. Потому выгоднее прокрутить все колёса/маски по куску массива размером с кэш L2, потом снова прокрутить дальше все колёса/маски по следующему куску массива, и так до конца массива. Так записи будут ограничены размеров куска массива (с кэш L2). Но понадобится хранить не только сами простые/маски, но и все позиции в которых колёса/маски остались к границе кусков, но это слёзы - простых надо прокрутить лишь $\pi(\sqrt{10^9})-1=3400$ штук.

-- 11.02.2026, 19:59 --

rockclimber в сообщении #1718080 писал(а):

Ну да, решето Причарда примерно так и работает.

По моему не совсем: тут нет увеличения размера колёс, они всегда ровно 30, как и 2 для только нечётных. Повторю, это гораздо больше похоже на работу только с нечётными, только модуль не 2, а 30, и потому возможных простых не 1, а 8.
Весь массив байтов можно представить как 8 одинаковых битовых массивов, в каждом из которых запускается своё решето Эратосфена для каждого простого до корня из миллиарда. Сами эти простые, 3398шт, удобнее получить не в процессе, а заранее, тем же решетом Эратосфена до корня из миллиарда, это быстро, а из большого массива их лишь вычёркивать.

Пример. Возьмём бит 1 из байта, он отвечает за +7 mod 30. Вычеркнем из битового массива длиной 1e9/30 все числа кратные 11. Первое число кратное 11 будет 187=30*6+7, это байт +6 в массиве (байты с +0 по +5 со смещением +7 не дают кратных 11 чисел), с него и начинаем вычёркивать, следующее число будет в +6+11=+17 байте, это 30*17+7=517, следующее число будет в +17+11=+28 байте, это 30*28+7=847, и так далее до конца массива. Каждый раз просто обнуляем бит 1 в каждом нужном байте не трогая остальные биты. И повторяем эту процедуру для всех простых до корня из миллиарда и для всех 8-ми битов в байтах. Только надо не вычеркнуть сами простые, т.е. 11 из примера, для этого начинаем вычёркивание всегда с байта +ceil(p/30), пропуская самое первое вхождение.

[rockclimber]

Dmitriy40 в сообщении #1718086 писал(а):

rockclimber в сообщении #1718080 писал(а):

Я планировал попробовать делать маски для своего алгоритма (выше описал) как раз такими, чтобы в L2 влезали (то есть сначала общая маска для чисел 3, 5, 7, 11, 13, 17, 19, потом для 23, 29, 31, 37, 41, потом 43, 47, 53, 59, 61, и так далее).

Это не лучший вариант: запись в память тормозит гораздо сильнее чтения памяти. Потому выгоднее прокрутить все колёса/маски по куску массива размером с кэш L2, потом снова прокрутить дальше все колёса/маски по следующему куску массива, и так до конца массива. Так записи будут ограничены размеров куска массива (с кэш L2). Но понадобится хранить не только сами простые/маски, но и все позиции в которых колёса/маски остались к границе кусков, но это слёзы - простых надо прокрутить лишь $\pi(\sqrt{10^9})-1=3400$ штук.

Тогда уточняющий вопрос: польза от кэша есть только тогда, когда в него влезают все данные (и числа, и маски)? После объяснений от чатгпт у меня сложилось впечатление, что если я работаю с двумя большими массивами, и один полностью слезает в кэш, а второй нет, то какое-то ускорение все равно будет. Или нет?

Dmitriy40 в сообщении #1718070 писал(а):

Для ориентирования, одна из самых быстрых программ primesieve, подсчитывает количество простых до миллиарда за 0.15с-0.2с и за 2с до 10млрд.

Установил, попробовал. Это прям реактивный самолет! У меня процессор, видимо, особенно шустрый, миллиард отрабатывает так, что даже не заметно.
Вот вывод для чисел до 100 миллиардов:

/usr/bin/time -v primesieve 100000000000 -c --threads=1 >/dev/null
Command being timed: "primesieve 100000000000 -c --threads=1"
User time (seconds): 12.36
System time (seconds): 0.00
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:12.39
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 5248
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 405
Voluntary context switches: 1
Involuntary context switches: 213
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

[Dmitriy40]

rockclimber в сообщении #1718092 писал(а):

Вот вывод для чисел до 100 миллиардов:

У меня (при запущенном фоном счёте):

C:\>primesieve 0 -d1e11 -t 1 -c
Sieve size = 128 KiB
Threads = 1
100%
Seconds: 19.376
Primes: 4118054813

Разница в скорости может быть из-за винды у меня.

rockclimber в сообщении #1718092 писал(а):

Тогда уточняющий вопрос: польза от кэша есть только тогда, когда в него влезают все данные (и числа, и маски)? После объяснений от чатгпт у меня сложилось впечатление, что если я работаю с двумя большими массивами, и один полностью слезает в кэш, а второй нет, то какое-то ускорение все равно будет. Или нет?

Разумеется лучше когда влезает всё. Ускорение от кэша будет почти в любом случае (если только массивы или их куски размером более размера кэша не используются строго однократно). Но если всё не лезет, то лучше впихнуть то что часто переписывается или много-много раз читается. Под впихнуть понимаю ограничить размеры (длину непрерывных обращений, не обязательно подряд, в любом порядке) чтобы процессор смог сам всё удержать в кэше. То что читается редко или всего пару-тройку раз в кэш класть не обязательно, кэш ускоряет лишь повторные обращения. Вот к примеру маски у Вас либо короткие (для простых чисел до десятков тысяч) и автоматом поместятся в кэш (если будут активно использоваться), либо столь разрежённые (сами же сказали что флаг плюс смещение), что в кэш поместятся лишь отдельные слова (по 64 байта) из них, где и стоит 1 (флаг простоты). А вот основной битовый массив постоянно не просто читается, а ещё и перезаписывается - как раз это и тормозит (я например видел что от одной команды записи в массив скорость падала в 10 раз).

[rockclimber]

Dmitriy40 в сообщении #1718093 писал(а):

Но если всё не лезет, то лучше впихнуть то что часто переписывается или много-много раз читается.

А, вот оно что! То есть именно основной массив туда лучше положить. А я все наоборот делал. Придется опять все переписывать

[mathpath]

Я пробую упаковать первый триллион простых в битовый массив
Дипсик меня убеждает, что в случае с растом для этого хватит 60 гигов оперативки
Принцип хранения такой:
Есть линейный массив битов (индексы 0, 1, 2, 3...).
Бит по индексу 0 отвечает за нечетное число 3.
Бит по индексу 1 отвечает за нечетное число 5.
Бит по индексу N отвечает за нечетное число (N * 2 + 3).
Я заставляю дипсик сгенерировать и сохранить на диске этот битовый массив
Он пыхтит два часа, пишет файл, а тот оказывается битый

[Dmitriy40]

mathpath в сообщении #1718916 писал(а):

Дипсик меня убеждает, что в случае с растом для этого хватит 60 гигов оперативки

А самому считать уже совсем разучились, даже с калькулятором? $10^{12}/2/8/2^{30}\approx58.2$ГБ.
Ну и Rust тут конечно же ни при чём.

mathpath в сообщении #1718916 писал(а):

Я заставляю дипсик сгенерировать и сохранить на диске этот битовый массив
Он пыхтит два часа, пишет файл, а тот оказывается битый

Не удивительно.
Попросите его выдать хотя бы десяток тысяч простых чисел, без всякой упаковки - точно сможет? Раньше у всех ИИ окно просмотра было меньше сотни и они не могли выдать даже просто 100 последовательных натуральных чисел ...

И кстати, какая у Вас скорость инета? А то получится что самому посчитать решетом Эратосфена будет быстрее чем скачать. У меня 200Мбит/с и качать дольше чем посчитать даже в один поток.

[mathpath]

Dmitriy40 в сообщении #1718948 писал(а):

И кстати, какая у Вас скорость инета? А то получится что самому посчитать решетом Эратосфена будет быстрее чем скачать. У меня 200Мбит/с и качать дольше чем посчитать даже в один поток.

А при чем здесь инет ?
Я пишу битовый массив локально на диск с помощью локальной же программой на расте
Один раз запишу, а потом буду его когда надо загружать в память
Генерить триллион простых эратосфеном дольше, чем прочитать бинарный массив с локального диска

[rockclimber]

Dmitriy40 в сообщении #1718948 писал(а):

mathpath в сообщении #1718916 писал(а):

Дипсик меня убеждает, что в случае с растом для этого хватит 60 гигов оперативки

А самому считать уже совсем разучились, даже с калькулятором?

Тут надо разобраться, что мы считаем...
Ибо запрос был

mathpath в сообщении #1718916 писал(а):

упаковать первый триллион простых в битовый массив

А у вас - все простые до триллиона... Дипсик, конечно, все перепутал, и ответил на ваш вопрос, а не на вопрос mathpath.

[Dmitriy40]

Да, я тоже перепутал, извиняюсь.

На первый триллион простых, т.е. практически до 3e13, надо 3e13/2/8/2^30=1746ГБ.

И как выше уже писал, хранение не по модулю 2, а по модулю 30, заметно уменьшает требуемый объём (до 931ГБ).

mathpath в сообщении #1718973 писал(а):

А при чем здесь инет ?
Я пишу битовый массив локально на диск с помощью локальной же программой на расте

Я неправильно понял Вашу фразу

mathpath в сообщении #1718916 писал(а):

Я заставляю дипсик сгенерировать и сохранить на диске этот битовый массив

- не ожидал что дипсик работает локально и сохраняет файл локально.
Да, чтение с диска обычно быстрее вычисления (хотя если файл фрагментирован и не на SSD, то могут быть варианты). Особенно если числа нужны не с 0, а скажем с 100500e12.