СЯУ

[stas]

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

Comments

[glocka.livejournal.com]

А зачем проверять, если можно просто заглянуть, есть ли данное число в таблице простых чисел полученных с помощью многочлена, перечисляющего множество простых чисел (http://dxdy.ru/topic13827-45.html)?

[stas]

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

[glocka.livejournal.com]

Пожалуйста, разъясните, какой метод заполнения этой таблицы по возрастанию и без пропусков самый эффективный. Ничего кроме как взять натуральный ряд и удалять кратные 2, 3 и т. д. в голову не приходит.

[stas]

А зачем нужен самый эффективный? Таблица никуда не денется, можно потихонечку заполнять.

[glocka.livejournal.com]

Т.е. как "зачем"?! Для Guinness World Records, конечно.