Имейте в виду, что я почти полный новичок в теории сложности.
Я читал о том, как AKS Primality показывает, что числа размера n могут быть показаны как простые или составные за полиномиальное время.Учитывая это, подразумевает ли это нахождение всех простых чисел, меньших числа n, также выполнимо за полиномиальное время, и, таким образом, алгоритм работает в FP.Кроме того, означает ли это, что подсчет всех простых чисел, меньших n, отсутствует в #P?
Любые идеи или комментарии приветствуются Спасибо!