Руст писал(а):
Уже есть и полиномиальный ( по количеству цифр или logp) aлгоритм проверки на простоту и учитывая, что следующее простое число не больше (хотя это ещё не доказано, а гипотеза)

получим, что алгоритм получения следующего простого закончится за полиномиальное время.
Для полиномиальности достаточно

. Этот факт вроде бы доказан.
Sonic86 писал(а):
Легко доказать, что нет элементарной формулы (плюс, умножить, возвести в степень) от одной переменной, которая принимала бы только простые значения.
Было бы любопытно посмотреть на доказательство.