В вики есть статья про решето Эратосфена – алгоритм нахождения всех простых чисел до некоторого целого р :
https://ru.wikipedia.org/wiki/Решето_Эратосфена
Там же описан псевдокод поиска простых чисел:

Вход: натуральное число n
Пусть A — булевый массив, индексируемый числами от 2 до n,
изначально заполненный значениями true.
для i := 2, 3, 4, ..., пока i2 ≤ n:
если A[i] = true:
для j := i2, i2 + i, i2 + 2i, ..., пока j ≤ n:
A[j] := false
Выход: числа i, для которых A[i] = true.

Есть упрощения алгоритма:
- поиск идет только по нечетным числам;
- поиск идет начиная с квадрата числа.

В комментариях к сообщению
https://habr.com/ru/post/124605/
нашел следующее упрощение:

«Также обычно рассматривают числа виде 6k, 6k+1, 6k+2,6k+3,6k+4,6k+5. Здесь 6=2*3 произведению первых двух простых чисел. Из них 6k, 6k+2,6k+3,6k+4 делятся на 2 или 3.
Поэтому надо проверять на простоту только числа вида 6k+1, 6k+5 (33.3% от всех).
Это можно обобщить: например, рассматривая числа вида 30k, 30k+1,…
Но это становится громоздким при программирование и дает малый выигрыш
30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19,30k+23, 30k+29 (26.6% от всех)»

Может быть, я что-то пропустил. Битовые варианты специально не рассматривал.

Пятничная задачка в следующем:
как ещё можно упростить (или усложнить!) как алгоритм, так и массив для алгоритма таким образом, чтобы за определенный период времени можно будет найти большее количество простых чисел.

alex55555Перебор здесь как бы давно сделан. Поэтому нужно сам принцип поиска менять.И я за то.

В одном из сообщений, как было сказано в первом сообщении данного топика:
авторЭто можно обобщить: например, рассматривая числа вида 30k, 30k+1,…
Но это становится громоздким при программирование и дает малый выигрыш
30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23, 30k+29 (26.6% от всех)»Здесь известны 8 реперных точек.

Если взять от 210k до 210k +209, то будет 46 реперных точек, и будет 22,7% от всех.

То есть, при определении простых чисел рассматриваются только 22,75 от всех чисел р.

Пока не вижу громоздкость.

В предыдущем сообщении ошибся - 43 реперные точки. И искать простые числа будем только среди 20,5% всех чисел.

Можно идти дальше.

Получаем 341 реперную точку для последовательности от 2310k+1 до 2310k+2309.
Применение этой последовательности позволит рассматривать только 15% всех чисел для нахождения всех простых чисел.

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

Поэтому, наверное, интересно найти новые приёмы по увеличению количества определяемых простых чисел за конкретное время.

Работа с блоками Ak+B позволяет уменьшить количество чисел (в процентном отношении), среди которых можно вести поиск простых чисел.

AklinGennadiy UsovА хочется увеличить количество определяемых чисел.Есть какая-то теорема вероятностной простоты числа. Вроде как доказанная математически, что для простого числа достаточно провести N(len) проверок и все, дальше с вероятностью 100% можно говорить что число простое.Хорошо. А сколько будет поверок?
Это хорошо для очень большого числа, а что будет с рядом стоящими?

Вот здесь как раз поможет "рамка" в виде блока Ak+B, которой "накрываем" область чисел над первоначальным числом.
И сразу будет видно, какие числа, которые находятся рядом с первоначальным числом, не надо будет рассматривать.

Dima TПроблема в том что сложность алгоритма не уменьшается. Начни перебирать вместо подряд каждого - каждое сотое потенциально простое число, получишь ускорение в сто раз, т.е. всего на два порядка, а надо как минимум на 50 порядков ускориться.А кто сказал, что можно посчитать все числа до ... даже представить сложно?

Уменьшили время расчетов в сто раз, значит в сто раз больше определили чисел. Уже хорошо.
Будем ещё что-то искать.

А почему Вы решили, что надо на 50 порядков? Может быть на 1000 порядков? Или на 10 порядков?
Что там говорит криптография?

kealon(Ruslan)Aklinпропущено...
Есть какая-то теорема вероятностной простоты числа. Вроде как доказанная математически, что для простого числа достаточно провести N(len) проверок и все, дальше с вероятностью 100% можно говорить что число простое. можно проверить, что на 100% непростое
называется Малая теорема Ферма А почему не применяют тест Ферма, когда надо определить много простых чисел.

Здесь говорится, что определили, что число - непростое, но не сказано, что число - простое.

BarloneGennadiy UsovЧто там говорит криптография?А что криптография, зачем там список всех простых? Для RSA нужно ровно два простых числа, причем очень больших и не сильно близких.Уже нашли эти числа?
Или нужны числа на каждый день?

maytonОткуда взято число 100?Вопрос к какому сообщению? И если не 100, то что?

Gennadiy UsovРабота с блоками Ak+B позволяет уменьшить количество чисел (в процентном отношении), среди которых можно вести поиск простых чисел.Можно далее строить блоки:
30030k+B,
510510k+B,
9699690k+B,
…..,
304250263527210k+B
и т.д.

При увеличении размера блока можно довести количество проверяемых чисел от всех чисел в последнем варианте до 3%.

Дальнейшее увеличение величины блока позволит дальше уменьшать процент количества проверяемых чисел в зависимости от всех чисел.

BarloneGennadiy UsovУже нашли эти числа?
Или нужны числа на каждый день?На каждый секретный ключГде можно найти алгоритм поиска секретных ключей (не программа)?

maytonЭто случайные числа.Нашли случайное, а оно не простое,
Где гарантия, что оно простое?

BarloneGennadiy UsovНашли случайное, а оно не простое,
Где гарантия, что оно простое? https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина А в этой статье написано:

"Однако, с его помощью нельзя строго доказать простоту числа".