Я специально поставил знак вопроса в названии топика, потому что не уверен, что представленные ниже формулы уже не применялись при поиске простых чисел.

Как известно, лучший метод поиска простых чисел – это решето Эратосфена.
Однако он медленный, и у него есть недостаток – идут повторы вычисления составных чисел. Например, 49 и 11 и 7 и 77. Причём, чем дальше – тем повторы увеличиваются в некоторой прогрессии, может быть, геометрической.

Предлагается новый метод (решето), когда составные числа вычисляются с помощью нескольких последовательных формул.
При этом практически нет повторений.
На диапазоне от 1 до 300 были получены все составные числа вида 6хК+-1.
Единственное повторение - 175 (разбираюсь).

Данный метод включает в себя несколько последовательных формул, которые будут иметь определённые ограничения, чтобы работать в диапазоне 6хК+-1.
В противном случае, при определённой доработке, данные формулы могут определять все числа числового ряда (это моё предположение, данный случай пока не рассматривал).

1. Первая формула, это
Р = А^2, где А >=5 для А из диапазона 6хК+-1
Эту формулу, конечно, применяли при определении составных чисел. Но эта формула мне нужна для дополнения других формул.

2. Вторая формула, это функция двух переменных 21844035
Р = (2*А)^2 - (1+2*B)^2 , А- целое, А>0, В - целое, В>= 0.
Или
Р = (2*А+1+2*В)*(2*А-1-2*В)
кому как нравится.
Всё зависит от того, какая из этих операций быстрее работает на компьютере.

В данном случае есть основное ограничение:
2*А > 1 + 2*В

В следующем сообщении попробую дать ограничения для формулы 2, чтобы высчитывать только величины 6хК+-1.

Будет ещё одна формула, пока дорабатывается.

Рассмотрим формулу
Р = (2*А)^2 - (1+2*B)^2

Расчет по такой формуле идет следующим образом:
для одного В вычисляются Р для всех возможных А таких, что Р =< М (граница диапазона от 1).

Если В=1, то чтобы получать числа величиной 6хК+-1, необходимо следующее условие:
А = 1+ 3*а, где а – целое число, а>=1.
и
А = 2+ 3*а, где а – целое число, а>=1.
В данной «колонке» происходит перемножение последовательных чисел из 6хК+-1 через одного:
5 и 11, 7 и 13, 11 и 17, 13 и 19, 17 и 23, и т.д.

Если В=4, то чтобы получать числа величиной 6хК+-1, необходимо следующее условие:
А = 1+ 3+3*а, где а – целое число, а>=1.
и
А = 2+ 3 +3*а, где а – целое число, а>=1.
В данной «колонке» происходит перемножение последовательных чисел из 6хК+-1 :
5 и 23, 7 и 25, 11 и 29, 13 и 31, 17 и 35, и т.д.

Тогда если (В-1) кратно 3, то, чтобы получать числа величиной 6хК+-1, необходимо следующее условие:
А = В+3*а, где а – целое число, а>=1.
и
А = В+1+3*а, где а – целое число, а>=1.

Дальнейшее изучение формулы 21845651 показало, что по сравнению с обычным решетом Эратосфена, при использовании этой формулы нет ничего нового. Всё те же повторы.

Однако у данной формулы есть преимущество:
с помощью данной формулы 21845651 определяются только нечётные числа.

Что помогает в решении задачи поиска простых чисел.

В сообщении 21845255 говорилось о том, что будет ещё одна формула определения составных чисел.

Есть формула
Р= х*у.
Можно эту формулу несколько переделать:
3*Р=х*(3*y).
Получается, что с помощью умножения на число (3) можно получить дополнительные составные числа.

Данную формулу можно расширить:
m*n*P = (m*x)*(n*y)

Таким образом, за счет чисел m и n можно создать множество составных чисел.

Теперь можно будет строить решето (метод) для определения составных чисел на некотором диапазоне от N1 до N2.

Данный метод заключается в последовательном поиске составных чисел среди нечётных чисел на диапазоне от N1 до N2.

Сначала необходимо на данном диапазоне исключить составные числа, которые получаются при умножении некоторых чисел на мелкие простые числа: 3, 5, 7, 11, 13, … К, где Л – последнее простое число, для которого имеет смысл проводить эту операцию.
В качестве предложения: К < (N2 – N1).

Для этого выполняются следующие операции :
Для каждого k из перечня К определяется остаток от деления N1 на k, после чего находятся составные числа в диапазоне с шагом k до N2.

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

Пусть очередное нечётное число Р.
Тогда определяем Q:
Q = sqrt(P)
Если Q – целое число, то это означает, что Р – составное число, у которого два сомножителя: Q и Q.
Если Q не является целым, то рассмотрим остаток q
q = А^2 – Р. А = (целое(Q) +1 )
И для этого остатка попробуем найти B:
B = sqrt(q) .
Если отличие двух сомножителей небольшое, то В – целое число, и определены два сомножителя.
В качестве примера этот алгоритм определил у числа 1606533434981 два сомножителя 1267501 и 1267481.

Далее будут рассмотрены следующие операции.

Gennadiy UsovВ качестве примера этот алгоритм определил у числа 1606533434981 два сомножителя 1267501 и 1267481.А затем алгоритм выдаёт ещё составные числа от -91 до +989 (можно больше) от исходного числа (второе и третье число – сомножители):

1606533435077 1267493 1267489
1606533435065 1267495 1267487
1606533435045 1267497 1267485
1606533435017 1267499 1267483
1606533434981 1267501 1267481
1606533434937 1267503 1267479
1606533434885 1267505 1267477
1606533434825 1267507 1267475
1606533434757 1267509 1267473
1606533434681 1267511 1267471
1606533434597 1267513 1267469
1606533434505 1267515 1267467
1606533434405 1267517 1267465
1606533434297 1267519 1267463
1606533434181 1267521 1267461
1606533434057 1267523 1267459

Согласно сообщению 21848245 легко находить сомножители для тех чисел, у которых эти сомножители почти равны.
Следовательно, необходимо рассмотреть возможность сделать так, чтобы сомножители были почти равны.
Например, умножить меньший сомножитель на 3, согласно 21848227 умножить на 3 и Р.
Например, есть
535507764991 1267501 422491
число и два сомножителя.
Но мы не знаем, что это число составное.

Умножаем основное число на 3 и получаем
1606523294973
После работы алгоритма получим
1606523294973 1267501 1267473
После чего делим второй сомножитель на 3, и получаем:
422491
То есть, число 535507764991 - составное число.

Одновременно получаем ещё несколько составных чисел.
535507765055 1267489 422495
535507765035 1267495 422493
535507764923 1267507 422489
535507764831 1267513 422487
535507764715 1267519 422485

alex55555Gennadiy UsovВ качестве примера этот алгоритм определил у числа 1606533434981 два сомножителя 1267501 и 1267481.А ещё бывают 3,4,5,6,... сомножителей.Данный алгоритм определяет только два сомножителя из всех возможных сомножителей.

Этого достаточно, чтобы сказать о числе Р, что оно составное.
То есть, строится некоторая окрестность (решето) числа Р, состоящая из составных чисел.
На полную факторизацию не претендую.

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

Имеется число 4566373287117,00
Корень этого числа 2136907,412

До величины корня существует около 146616 простых чисел, которые, допустим, неизвестны.

Спрашивается в задачке:
Сколько нужно сделать вычислений, чтобы понять, что это число составное?

BarloneGennadiy UsovИмеется число 4566373287117,00 Корень этого числа 2136907,412
До величины корня существует около 146616 простых чисел, которые, допустим, неизвестны.
Спрашивается в задачке:
Сколько нужно сделать вычислений, чтобы понять, что это число составное? СоставноеА какое максимальное число может "проглотить" pow(2,4566373287117-1,4566373287117)?

BarloneGennadiy UsovА какое максимальное число может "проглотить" pow(2,4566373287117-1,4566373287117)?Большое. Для числа с 5000 десятичных знаков еще можно дождаться результата (несколько минут). Для чисел порядка используемых в RSA криптографии ответ за меньше секунды.Тогда, получается, нет проблем с выбором простого числа рядом со случайным числом для RSA?

И тогда зачем поиск любого решета?

BarloneGennadiy UsovА какое максимальное число может "проглотить" pow(2,4566373287117-1,4566373287117)?Большое. Для числа с 5000 десятичных знаков еще можно дождаться результата (несколько минут). Для чисел порядка используемых в RSA криптографии ответ за меньше секунды.Получается, что формируется число 2^(4566373287117-1), которое представляет собой двоичное число, длиной (4566373287117-1), у которого первая цифра 1, а остальные цифры 0.

И надо найти остаток от деления этого числа на 4566373287117.

Так какие проблемы?
Почему такая медленная скорость для чисел в районе 5000 десятичных знаков?
Ведь "питону" любые длины чисел до лампочки?

maytonGennadiy UsovВедь "питону" любые длины чисел до лампочки?Ему может быть до лампочки конструктор целого числа. Но операции над ним - скорее всего нет.Так почему всё-таки:
Barlone Для числа с 5000 десятичных знаков еще можно дождаться результата (несколько минут). Наверное, есть ограничения?