Как найти n-е простое число со сложностью o (1)

Question

Как найти n-е простое число со сложностью o (1)

Answer 1

Единственный способ сделать это в O (1) - это массив всех простых чисел. Таким образом, вы сможете поддерживать только определенное число в зависимости от памяти вашего компьютера.

Edit:

Возможно, есть какой-то способ вычислить это, используя кучу исчислений, но это вне меня:)

Answer 2

Вы не можете.На самом деле, вы не можете перечислить простое число без тщательного поиска.

Если у вас есть база данных со всеми простыми числами до n , вы можете выполнить поиск по nth простое число (до n ) в o(log n).

Answer 3

Чтобы найти n-е простое число в фиксированное время, подразумевается, что существует разумная формула для вычисления pi (n) (возврат n-го простого числа). См. http://primes.utm.edu/notes/faq/p_n.html для предварительного обсуждения этой темы.