Вероятность и теория чисел.

[Руст]

vbn писал(а):

Получается, что для $p_{1077870}=16 777 213<2^{24}$ программа перемножает все простые вплоть до $p_{1077869}=16 777 199.$
Следовательно, программа имеет дело с числами вплоть до $\alpha>2^{\pi (p_{1077869})}=2^{1077869}>10^{300000}$.
Руст, это действительно так?

Да перемножает, только большие числа не получаются, так как перемножает по модулю p, (в этом случае остатки останутся не больше 16777216) и только в случае деления M(x)+1 для некоторого из них производится умножение по модулю p^2. В последнем случае при перемножении числа останутся в пределах 72 бита, а остатки в пределах 48 бит. Я же написал алгоритм, где всё это ясно сказано.

[vbn]

Руст, на ЛС вы не ответили, повторю просьбу здесь:
не могли бы Вы сбросить исходники Вашего алгоритма на happiless sobachka yandex tochka ru?

[maxal]

Статья из свежего Мат.Просвещения: В. А. Успенский Четыре алгоритмических лица случайности.