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$ Commented 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$ Commented 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$ Commented 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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.