Какой самый эффективный алгоритм для выдачи простых чисел, вплоть до очень высоких значений (все 32-битный компьютер может обработать)

Question

Моя программа должна зацикливаться вечно и выдавать через печать все простые числа, с которыми она сталкивается. Делаем это в x86-NASM, кстати.

Моя первая попытка делит его на КАЖДОЕ предыдущее число, пока либо Carry не станет 0 (не простое число), либо результат не станет 1.

Моя вторая попытка улучшила это, только проверяя каждую секунду, поэтому только нечетные числа.

Третье, что я сейчас реализую, - это попытка не делить КАЖДОЕ предыдущее число, а скорее на все предыдущие, деленные на 2, поскольку вы не можете получить четное число, разделив число на нечто большее, чем его половина

Еще одна вещь, которая может помочь, это проверить ее только с нечетными числами, например, сито с эратосфенами, но исключая только четные числа.

В любом случае, если я могу сделать что-то еще, вся помощь, добро пожаловать.

редактирование:

Answer 1

Если вам нужно проверить несколько простых чисел, то тест простоты AKS *1002* имеет полиномиальную длину n.
Если вы хотите найти очень большое простое числокриптографического размера, затем выберите случайный диапазон нечетных чисел и просеивают все числа, чьи коэффициенты являются небольшими простыми числами (например, меньше чем 64K-240K), затем проверяют оставшиеся числа на простоту.

Если вы хотите найти простые числа в диапазоне, тогда используйте сито , сито из Erathostenes очень легко внедрить, но оно работает медленнее и требует больше памяти.
Сито Аткина быстрее, сито колес требует гораздо меньше памяти.

Размер проблемы экспоненциальный, если подходить наивно, поэтому перед микро-оптимизацией обязательно сначала выполнить макро-оптимизацию.
Более или менее все алгоритмы простых чисел требуют уверенности в Теория чисел , поэтому обратите особое внимание на группу / кольцо / поле, над которым работает алгоритм, потому что математики пишут такие операции, как обратное или умножение с одним и тем же символом, для всех алгебраических структур.

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