Можно ли проверить, является ли число простым или нет в O (logn)?

Question

Я читаю конкурентоспособную книгу программирования в течение одного месяца Книга написана одним из мировых финалистов нашей страны (Бангладеш). Следует отметить, что книга написана на нашем родном языке (бенгали), и это не так популярно во всем мире. Из-за наличия контента на бенгальском я не могу сослаться сюда. Вот почему я извиняюсь прежде всего.

В главе «Теория чисел» этой книги дано много алгоритмов для проверки Primality. Наиболее оптимальным он показал, это «Сито Эратосфена» в О (нлоглогн). Но он написал одну строчку. Я перевожу это. «Существует более эффективный метод проверки простоты в O (logn). Подумайте сами.

Я гуглил об этом. Но я не нашел ничего удовлетворительного.

Действительно ли возможно проверить простоту числа в O (logn) ?? И если это возможно, то до какого диапазона можно сделать вывод ??

Answer 1

Неверное утверждение.Для числа N количество цифр равно O(log N), поэтому утверждение означает, что существует алгоритм, который линейный по количеству цифр.Самый известный результат - полином по количеству цифр.(Тест первичности Агравала-Каяла-Саксены, Õ (logN ¹² ). Это логин степени двенадцати, а не одного.

Тем не менее, Õ (logN ¹² ) ⊂ O (N)