0
$\begingroup$

Bear in mind I'm almost a complete noob at complexity theory.

I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, does that imply finding all prime numbers less than a number n is also doable in polynomial time and thus the algorithm runs in FP. Additionally, does this imply that counting all primes less than n is not in #P?

Any ideas, or comments are appreciated Thanks!

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ The number of primes in $\{1, \ldots, n\}$ is $\theta(\frac{x}{\log x})$, which is more than polynomial in the length of $n$. Simply listing the primes would take too long. $\endgroup$
    – Reinstate Monica
    Jun 24, 2018 at 2:24
  • $\begingroup$ You can list the primes less than $n$ in $O(n^k)$ (for some $k$), but not in $O(\log^k n)$. Usually, in number theory, it's the latter which is called "polynomial time", not the former, since $n$ is exponential in the number of digits. $\endgroup$
    – chi
    Jun 24, 2018 at 9:17
  • $\begingroup$ In order to count the number of primes ≤ n, you wouldn't test each of them from primality. If you could test for primality in O(1), which you can't, then counting the primes ≤ n would take \Theta(n) time, but it can be easily done in O(n / log n) or O (n / log^2 n), a bit harder in O (n^(2/3)) and AFAIK there is an algorithm running in O(n^c) for some c ≈ 0.52 or so. Of course this is polynomial in n, not in the size of n. $\endgroup$
    – gnasher729
    Oct 31, 2022 at 9:19

2 Answers 2

Reset to default
4
$\begingroup$

No, it doesn't. There are exponentially many primes less than $n$, so you can't enumerate them in polynomial time.

Improve this answer
$\endgroup$
1
$\begingroup$

The answer by D.W. already points out that listing all primes up to $n$ cannot be done in time polynomial in the representation of $n$.

It can be done in time polynomial in $n$, though. Using the sieve of Eratosthenes, the running time is $n\log n$.

You had one other question: Whether counting primes can be done in #P. Yes, it can. This is a direct consequence of having a PTIME primality test. (And it would not have been contradicted by (listing or) counting being in FP, as FP is a subclass of #P.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.