Нахождение всех простых чисел от 1 до n, алгоритм

[Echo-Off]

Руст в сообщении #136427 писал(а):

При выполнении обобщённой гипотезы Римана достаточно перебирать простые а

Это Вы про что, простите? Перебирать для чего?

[Руст]

Это при проверке является а свидетелем псевдопростоты $n=2^st+1$ или нет.
Пробегаем по простым a от 2 до $2(\ln n)^2$ и вычисляем $b=a^t\mod n$.
Если это число 1, то а свидетель, если нет проверяем $b,b^2,..,b^{2^{s-1}}\mod n$. Если среди этих чисел есть -1(или то же самое n-1), то а свидетель, иначе n - составное.
Согласно ОГР для простоты n достаточно проверить по a от 2 до $N=2(\ln n)^2$, На самом деле для проверенных чисел до $10^{15}$ число N существенно меньше достаточно проверять для a=2,3,5,7,11,13.

[Spook]

Руст, а числа $s,t,a$ как-то находятся? Просто не понятно, как их определять. Или такое представление единственно? Расскажите, пожалуйста, или дайте ссылку, где про это можно почитать.

[Руст]

Spook писал(а):

Руст, а числа $s,t,a$ как-то находятся? Просто не понятно, как их определять. Или такое представление единственно? Расскажите, пожалуйста, или дайте ссылку, где про это можно почитать.

Проверяется на простоту нечётное число n. Соответственно n-1 чётное. Делим это число на 2 до тех пор, пока не получится в результате нечётное число и обозначим это через t. Число s равно количеству делений на 2.

[Spook]

Руст, спасибо, понял.

Материала набрал много, осталось поразбираться. Вопрос решен, всем спасибо.