maytonGennadiy UsovЯ уже приводил чередование 4 и 2 21952153 .
Накопление простых в массиве может когда-то прекратиться.(на больших числах)А тебе много и не надо. Накопи простых хотя-бы тыщу.
Большая часть делителей отбивается на самых ранних шагах.Можно применить "ленивый алгоритм накопленных простых чисел".
О нём уже было сказано 21954752 .
Поскольку там ошибка, привожу ещё раз (без ошибки)
В массив можно записать хоть 1000 чисел.

maytonВ своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.По этому поводу можно рассмотреть такой вариант.

Квадраты последовательных чисел N и (N + 1) отстоят друг от друга на (2*N+1).
Поскольку делители - только нечётные числа, то N и (N + 2) отстоят друг от друга на (4*N+4).

Итак, в начале находим корень минимума диапазона, от целого этого числа получаем "квадрат N",
и это будет точкой отсчета по смене величины, которая ограничивает количество делителей.

Осталось проверять расстояние исследуемого числа от предыдущего "квадрата N",
и если получаемое расстояние превышает (4*N+4) от этого "квадрата N",
то определяется новый "квадрат N+1", равный увеличению предыдущего "квадрата N" на (4*N+4).

maytonПочему 22 ?Очень удобно в одном массиве в ячейке [0] помещать длину массива данных,
и "работать" с массивом, начиная с ячейки [1].

Мы ведь привыкли считать: 1,2,,,,,,n,
а не 0,1,2,,,,,(n-1)

И притом, нужна будет отдельная переменная для хранения количества данных в массиве.

Кстати, я уже это демонстрировал на предыдущих топиках.

Решил ещё раз поработать с тестом Миллера-Рабина с точки зрения:
какой перечень остатков выдаёт этот тест.

Пока поработал с числами до 115.

Есть простые числа, для которых только 1 или n-1 по двум условиям теста:
7, 11,19,23,31,43,47,59,67,71,79,83,103,107

Есть простые числа, для которых только 1 или n-1 по двум условиям теста не для всех случайных чисел:
29,37,41,61,73,89,101,109,113

Есть простые числа, для которых только 1 или n-1 только по второму условию:
5,13,17(не все),53,97(не все),

Есть составные числа, для которых только 1 только по второму условию:
39, 105.
Поэтому по второму условию значение 1 не подходит.

Barlone,

Вопрос не в том, как получаются псевдопростые числа.

Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.

maytonЕсли бы мы знали как разделить область определения Миллера-Раввина на детерминированную и случайную то получили бы две функции.
Причем одна из них была бы строго детерминирована по определению.Пример 21957887 показал, что тест Миллера-Раввина находит среди чисел Мерсенна только простые числа без пропусков,
причем только с помощью первого условия.
Правда, медленнее теста Люка-Лемера раза в 2-3.
Это уже область применения без появления составных чисел.BarloneGennadiy Usov,
Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.Увеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример - 21956300 ),
из-за которых эти числа принимаются тестом как простые.BarloneGennadiy UsovBarlone,
Вопрос не в том, как получаются псевдопростые числа.
Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.
Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.Вопрос как раз в том, как получаются псевдопростые.При исследовании теста Миллера-Рабина (может быть и других тестов)
необходимо для каждого составного небольшого числа (как примера) отследить появление условий 1 или (n - 1),
частоту их появления и тогда принимать какие-то решения по этим результатам.
Например, есть числа 21958523 , для которых тест Миллера-Рабина показывает только 1 или (n - 1) по двум условиям.

Здесь можно говорить о подмножестве простых чисел, для которых существует достаточное условие (примерно как в 21907153 ).BarloneЯ могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)С удовольствием прочитаю.

У меня 2 вопроса ( с учетом примера 21956300 ) для чисел 2047 и 2053:

Пока для первого условия теста Миллера-Рабина:

для числа 2047 (составное) после нескольких раундов (выбор случайного числа) появляется 1.
Это означает, что число 2047 псевдопростое?

для числа 2053 (простое) в течении нескольких раундов (выбор случайного числа) не будет появляться 1.
Это означает, что число 2053 составное?

Решил "отбросить" поиск случайного числа для первого условия теста Миллера-Рабина
и заменил этот поиск на перебор вариантов от 2 до (n - 2). Для чисел до 115 - не так много информации.

Оказалось, что:

1. Есть числа, у которых в остатке (по модулю) получается только 1 и (n - 1).
Множество таких чисел уже может быть подмножеством простых чисел.

2. Есть числа, которые мы считаем простыми,
у которых в остатке (по модулю) значения 1 и (n - 1) составляют от 70% до 5% от общего перечня остатков.
Для некоторых из этих чисел трудно будет найти значение 1.

3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается только 1.
В разных числах 1, 2, 5 значений.

4. Есть числа, у которых при переборе от 2 до (n - 2) остатки (по модулю) то же плавно возрастают от 2 до (n - 2).

Ошибся.
пункт 3 предыдущего сообщения надо читать так:

3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается иногда 1.
В разных числах 1, 2, 5 значений.

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

По другому коду или по алгоритму?

maytonЕсли ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне: