maytonГоворишь загадками. Какой блок? Сколько у тебя получилось?Мне удобно работать блоками по 50 000 000 чисел. Это видно по программе. Следующий блок от 50 000 005 и ещё 50 000 000 чисел. И т.д.

В первом блоке определилось 3 001 132 простых чисел.
От 50 000 005 (начало второго блока) до 68 200 187 найдено 1 017 273 простых числа.

Итого на диапазоне от 5 до 68 200 187 было найдено 4 018 405 простых чисел.

maytonТеперь поговорим об оптимизациях.
Вырожденный Миллер Рабин превращается в метод грубой силы?
Или нет?Тест Миллера-Рабина (сами формулы) остаётся в силе.

Просто меняется последовательность поиска параметров для формул теста Миллера-Рабина.

В эвристическом алгоритме:
Для 50 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина.
Для других 25 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина, а также иногда имеет место 2-й этап (автоматически) - ещё 9 раундов (автоматически - может быть меньше) .
И т.д.

По тесту Миллера-Рабина:
количество раундов равно log( p ).
И считать по двум формулам,
И то - то ли простое число, то ли нет.

Разница есть?

Это для начала оптимизации...

Ещё одно наблюдение при тестировании программы.

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

Решил проверить программу на числах 2^1024.

Для этого поменял немного заставку программы - смотрел 5000 чисел после 2^1024:



Получилось:

Так что, критика и обсуждения закончились?

А как же дежурные фразы, mayton 21908442 ?

maytonСколько времени он у тебя работал?Эвристический алгоритм для формул теста Миллера-Рабина окончательно "сформировался" дня три назад.

До этого были пробные тесты для s = 1, для s = 2, для s = 3.
После этого был пробный тест для всех s.

Поскольку ПК - старенький, то прогон проводился для отдельных s до 250 000 00, а для всех s - до 68 000 000.
Стараюсь запускать программу тогда, когда нахожусь рядом.

Поскольку для небольших n всё проходит, то наступает "эвристика". Можно распространять на большие числа.

В частности, был прогон для чисел около 2^1024.

maytonНадо оценить асимптоматику.
Не вычислить. А именно оценить.
Для этого надо сделать штук 5 запусков
С линейно меняющимся параметром
И засечь с точностью до секунд время.
После этого посмотреть в Экселе график
И прикинуть что это. Полином? Экспонента? Etc.Ваши предложения по диапазонам?

Нужно ли предварительное деление?

Нужен ли предварительный тест Ферма?

Основные параметры эвристического алгоритма:
- число значений s2;
- число раундов при одном s2, после которого узнаём, что число составное ( остаток не равен ни 1, ни (n - 1))
- число значений s2, после которых определяется простое число.

По каждому значению можно определить мax или min на некотором интервале чисел (у меня либо 200000, либо 1000000).

maytonВыше ты делил по 50 лимонов.
Вот пускай так и будет.
По Ферма не понял. Мы ведь один алгоритм обсуждаем? Или несколько?Ферма по любому быстрее определяет множество чисел, среди которых все простые числа.

Ведь тест Ферма - это один раунд.
Тест Миллера-Рабина - это несколько раундов.
Причём, это по всем числам: и составным, и простым.

Мне видится следующий подход: тест Ферма ограничивает количество чисел, среди которых все простые числа,
а тест Миллера-Рабина (с эвристическим алгоритмом или с другим алгоритмом) "зачищает" полученные числа,
выбирая из них только простые числа.

Это моё видение процесса поиска простых чисел,
при этом ещё в начале процесса поиска - деление на небольшие множители.

Можно рассмотреть вопрос применения одного эвристического алгоритма для формул теста Миллера-Рабина,
и сравнить результат применения алгоритма с результатами теста Ферма.

Сейчас у меня заканчилась работа программы для второго диапазона: от 50 000 005 до 100 000 005.
На этом диапазоне получено 2760321 простых чисел.
Программа не ошиблась - среди полученных простых чисел нет составных чисел.

Вначале программы идёт проверка на множители до 643 (так решил),
далее тест Ферма,
далее алгоритм.

И даже в таком виде диапазон из 1 000 000 чисел рядом с числом 100 000 000 программа "проходит" за 3 минуты.

Применение множителей и Ферма, как я уже говорил ранее,
позволило уменьшить количество изменений значений s2 для одного числа до 4 (ранее были случаи 7 ).

Основное значение количества раундов (а1) при одном значении s2,
когда выявляется составное число, в основном - значение 3,
но есть случаи, когда встречается значение 5, очень редко 7.
(обращаю внимание - значения нечётные)

Убрал все добавления, оставил один эвристический алгоритм.

Программа считает.
На 2 000 000 чисел 148932 простых.
Время работы 1,5 минуты.
Программа продолжает работу...

maytonГеннадий? Куда-то пропал. Или построение 5 измерений так долго?Не пропал.

Продолжаю считать. Уже прошёл (с остановками) число 153 000 000.
Есть интересное число 133800661, разбирался с ним.

maytonТак долго? Ладно побей на интервалы поменьше.В начале на диапазон в 1 000 000 чисел уходило 1,5 минуты.
На отметке 175 000 000 уходит уже 2,5 минуты

maytonНу дык... цифры есть? 4-5 штук.Сейчас основные цифры, которые печатаются после мини диапазона (1 000 000), это:
- на каком раунде (а1) выявляется составное число (максимальное по мини диапазону);
- сколько может быть значений s2 (максимум на мини диапазоне) - дополнительные 9 раундов на каждое значение.

На текущий момент max a1 - очень редко 7, один раз - 11,
а для s2 - почти всегда 4.

Прошел 250 000 000.

В конце этого диапазона время обработки мини диапазона увеличилась до 3 мин. 09 сек.

На текущий момент max a1 - очень редко 7,
а для s2 - почти всегда 4, редко 5,6, один раз 8.