# 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. Jun 24, 2018 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, 2018 at 9:17
• 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. Oct 31, 2022 at 9:19

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