Asymptotically there is around $\frac{n}{\ln n}$ primes below a given integer $n$. Thus $\frac{n}{\ln n}$ is a lower bound for the time complexity of any algorithm that at some point finds each prime below $n$.
Some algorithms find the number of primes below $n$ without listing all the primes below $n$. Time complexity around $O(n^{\frac{2}{3}})$ is attainable see https://github.com/kimwalisch/primecount
Is there a way to find the sum of all primes below $n$ without listing them all?
