Можно ли найти все простые числа меньше n, выполнимые за полиномиальное время?
Имейте в виду, я почти полный новичок в теории сложности.
Я читал о том, как AKS Primality показывает, что числа размера n могут быть показаны как простые или составные за полиномиальное время. Учитывая это, подразумевает ли это нахождение всех простых чисел, меньших числа n, также выполнимо за полиномиальное время, и, таким образом, алгоритм работает в FP. Кроме того, означает ли это, что подсчет всех простых чисел, меньших n, не входит в #P?
Любые идеи или комментарии приветствуются Спасибо!
1 ответ
Что ж. То, что aks говорит, что проверка простоты для числа n - это O (b^k), где b = log2 (n), а k - некоторое целое число. Итак, если ваши вопросы перечислены все простые числа от 1 до n также O (b^k). Тогда ответ тривиально отрицательный, потому что количество простых чисел меньше n равно O(n/logn). Поэтому вам потребуется O(n/log(n)) только для их перечисления. Если ваш вопрос заключается в том, существует ли ak такое, что сложность перечисления всех простых чисел, меньших n, составляет O(n^k). Тогда ответ тривиально да, потому что самая тривиальная форма решета — это O (n ^(1.5)). Если что-то неясно, пожалуйста, дайте мне знать