Is there any other method or trick to find pi(x)[no. of primes upto x]other than the formula given by Euler..? (The other question is on prime arithmetic progressions.)
$\endgroup$ 21 Answer
$\begingroup$Values of π(n) have been calculated up to n = $10^{26}$. For a simple method that is significantly faster than just finding all the primes using a sieve and counting, you can look up Legendre's method for example here: Legendre's method is quite simple. Faster methods run in $O (n^{2/3+\epsilon})$.
The "trick" is to avoid actually finding all the primes, if all you want to know is how many there are.
$\endgroup$
