Начало тут:
topic62419.htmlА то пропадает почему-то все.
Ну, и наконец, самое вкусное - элементарное нахождение любых больших простых чисел

Допустим, мы хотим найти простые числа порядка

(или

- без разницы)

Шаг -2. Возьмем "удобное число"

соответствующее искомому порядку. Это нечетное число, которое можно представить в том же, упомянутом выше, виде

.
Шаг -1. Выделим его четное основание

и назовем его

. У нас оно будет равно

. Это наше основание. Это нижняя граница области в которой мы получим большие простые числа.
Шаг 0. Зададим верхнюю границу области больших простых чисел, как дельту

. Например, 1000 (

). Т.е., мы задали диапазон

.
Теперь вспомним еще раз, что если мы приведем уравнение к виду

и будем последовательно фиксировать

(y=1,2,3,4,5...), то получим выражения вида

, или

,

, или

,

, или

,

, или

,

, или

,

, или

,

, или

,
и т.д.
Наше число

(

) - это число вида 10000....0000, т.е., сумма его цифр равна "1". Соответственно, число

- делится на "3".
Мы нашли

.
Возьмем

(

определяется как число, которое делится на

, плюс

, где

- номер шага итерации) и "пойдем прибавлять" наш первый шаг равный 3. Получим

,

,

и т.д. Заполняя "вычеркиванием" таблицу от

до

. Т.е.,

. Видите, величина самого

нас не волнует - мы работаем в области от 1 до

На следующем шаге, используя признак делимости на 5, мы можем найти

- это само число

. Откуда новое

. Если хотим, можем взять

"за пределами области

":

. И снова "пошли прибавлять"

, получая

,

,

,

и т.д.
Используя признаки делимости и благодаря тому, что мы взяли "удобное число" можно "просеять" нашу область решетом из первых нечетных чисел.
А что с большими нечетными?
А очень просто.
Вот, взяли мы на шаге "209" очередное нечетное число "419". (метод будет одинаков для любой разрядности числа)
Нам не надо искать особые способы проверки делимости какого-то большого числа около

на 419.
Мы просто:
1) выделяем в этом числе степень 10 (определяем разрядность числа - p).

2) домножаем это число на степень

. Получаем число

. Это число точно делится на 419 и находится "недалеко" от

.
3) насколько "недалеко"? Представляем его как

. Получится число 581000000... (с 9997 нулями).
дальше, пока, для простоты, предположим, что нас такая близость "устроила".
4) берем "смещение" этого числа, равное шагу итерации, т.е., "209". Получаем

, т.е., 5810000...(9994 нуля)...0000209. Это наше новое

. И опять "пошли складывать" по 419

. При этом проверяя, сначала старшие разряды - пока сумма не достигла

, нас число не интересует. Когда сумма стала больше

на некоторое

, берем новое

и продолжаем "просеивать" нашу искомую область

. Естественно, что как только

, то с данной итерацией мы закончили и переходим к следующей.
Этот алгоритм универсален для любой разрядности, поэтому признаками делимости на 3, 5 и т.п. можно и не "заморачиваться".
"Просеянная" область от 1 до

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

(которое у нас было "за скобками"), домножьте их на 2 и прибавьте 1 - вот ваш "улов" простых. И в нем, думаю, далеко не одна "рыбка" (да не золотая, а самая что ни на есть простая!)

Данный алгоритм не использует ничего, кроме сложения (единственное вычитание - это дополнение до следующего разряда 10 и может быть реализовано через сложение). С точки зрения обычных приложений на домашнем компьютере мы ограничены разрядностью чисел над которыми можно делать операции стандартными средствами. Но можно использовать специальные программные библиотеки для работы с большими числами или реализовать поразрядное сложение в строковом виде. А число операций сравнительно невелико.
Таким образом, даже на домашнем компьютере можно за приемлемое время получить очень большие простые в заданном диапазоне, не требующие дополнительных проверок.
Ну, а теперь вернемся к шагу 3. Здесь есть место для оптимизации.
Когда мы получили

, в нем

разрядов одних нулей, которые мы будем вынужденно "пробегать" сложением по 419.
Эту задачу можно упростить в двух направлениях.
1. Мы можем циклически прибавить к

более младшие степени

.
Т.е., мы из числа вида "70000000000000000000" можем сразу получить число вида "77777777777777777777", которое будет ближе к

на целых.. на много, в общем, ближе

2. Мы можем "проапгрейдить" алгоритм более сложными операциями, если будем высчитывать - насколько нацело делится

на очередное число нашей итерации и брать остаток от деления

, представляя

(где

- шаг нашей итерации).
Степень вычислительной сложности первого и второго способа лучше оценят более сведущие специалисты, чем я

Возможно оптимальнее всего будет использовать сочетание этих алгоритмов.
Да, и количество итераций у нас будет не

, конечно

Если в уравнении

,

, то

, откуда грубая оценка для

, при больших

такова, что

. Если точнее, то

, но достаточно взять целую часть от

в качестве номера последней итерации.
Ну, и на самый конец

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

для заданного

в натуральных

и

, то перед нами - самый простой тест на простоту любого числа

Вот, таково наше с Сундарамом решето
