Поиск простых чисел - Отсев чётных чисел

[Star Cat]

Поиск простых чисел - Отсев чётных чисел
Задача
Допустим нам известно простое число 31. Необходимо найти следующее число.
Этап №1 – поиск простых делителей
Первое нечётное число: 3. Поэтому делим $31/3=10$ и отбираем простые числа от 3 до 10. Это 3, 5, 7.

Этап №2 – вычисление остатка
Делитель №1) $31/3=10$, остаток - 1
Делитель №2) $31/5=6$, остаток - 1
Делитель №3) $31/7=4$, остаток - 3

Этап №3 – отсев чётных чисел
Например, размер шага равен 10, то есть ищем от 32 до 41.
У делителя №1 - 3, остаток – 1, $3-1=2$. Зачёркиваем номера из 10ка начиная с двойки: 2, 5, 8, новый остаток – $10-8=2$. Оставшиеся чётные числа: 4, 6, 10.
У делителя №2 - 5, остаток - 1, $5-1=4$. Зачёркиваем номера из 10ка начиная с четвёрки: 4, 9, остаток – $10-9=1$. Оставшиеся чётные числа: 6, 10.
У делителя №3 - 7, остаток - 3, $7-3=4$. Зачёркиваем номера из 10ка начиная с четвёрки: 4, новый остаток – $10-4=6$. Оставшиеся чётные числа: 6, 10.

Проверка
Осталось два чётных числа: 6 и 10.
1) $31+6=37$. Поскольку число увеличилось, то количество простых делителей так же могло увеличиться. $37/3=12$. Ищем от 11 до 12. Это 11. Проверяем $37/11=3$, остаток – 4. Значит 37 - первое простое число!
2) $31+10=41$. $41/3=13$. 13 – простое число. Проверяем $41/13=3$, остаток – 2. 41 - второе простое число!
Найдено два простых числа: 37, 41.
ЗАДАЧА РЕШЕНА!

Итог
Чтобы продолжить поиск надо суммировать 31 и размер шага: $31+10=41$ – новая точка отсчёта. И повторить этап №3, добавив два новых делителя 11, 13.
Преимущество данного метода в том, что найденное простое число не нуждается в проверке поскольку, при его поиске использовались все возможные делители. К тому же легко перейти к поиску следующего числа.
4 января 2018 г.

[Brukvalub]

Star Cat в сообщении #1281237 писал(а):

Преимущество данного метода в том, что найденное простое число не нуждается в проверке поскольку, при его поиске использовались все возможные делители. К тому же легко перейти к поиску следующего числа.

У этого метода нет никаких преимуществ, это излишнее усложнение древнего метода решета Эратосфена, к тому же косноязычно и мутно записанное.

[vorvalm]

Star Cat
$198406007$ - простое число, найдите следующее простое число.

[Star Cat]

vorvalm в сообщении #1281289 писал(а):

Star Cat
$198406007$ - простое число, найдите следующее простое число.

Какой смысл его искать?

[Someone]

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

[Star Cat]

Someone в сообщении #1281325 писал(а):

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

Мне нужен список простых чисел до 66135335.

[Pphantom]

Star Cat в сообщении #1281329 писал(а):

Мне нужен список простых чисел до 66135335.

Я сейчас так, интереса ради, написал простейшую реализацию решета Эратосфена. Написание кода заняло примерно 3 минуты, выполнение - около 2 секунд. Вы уверены, что на оптимизацию такой задачи (даже если оная будет успешной) стоит тратить более получаса?

[Someone]

А зачем такой большой? Для решета Эратосфена обычно достаточно иметь список простых, не превосходящих квадратного корня плюс ещё пара на всякий случай.

Star Cat в сообщении #1281237 писал(а):

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

Числа, оставшиеся после применения решета Эратосфена, тоже гарантированно простые. При этом оно явно проще вашего метода.

Но мне непонятно, зачем это? Какую цель Вы имеете в виду? В криптографии нужны большие простые числа порядка $10^{100}$ и больше. Ясно, что ни решето Эратосфена, ни ваш метод не позволяют находить такие числа. В то же время есть методы, с помощью которых такие числа находятся очень быстро.

[Degen1103]

Цитата:

...Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?
Пришла в голову идея записывать в файл не сами числа, а расстояния между ними. А расстояние между соседними простыми числами всегда должно быть небольшим, предположил, что уместится в один байт...

База данных простых чисел

[Lia]

Degen1103
Проблема хранения простых чисел ТС не волновала.