# Is finding all primes less than n, doable in polynomial time?

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!

• 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. – Reinstate Monica Jun 24 '18 at 2:24
• 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. – chi Jun 24 '18 at 9:17

No, it doesn't. There are exponentially many primes less than $n$, so you can't enumerate them in polynomial time.
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$.