Number Of Primes

The number of prime numbers not exceeding a given number n is a mathematical function, PrimePi[n] in WolframMathematica? notation; it equals approximately n/(log n). Conversely, k-th prime is approximately k*(log k) in magnitude (very roughly, but sufficiently so for asymptotic complexity calculations).

For more precise formulations look up PrimeNumberTheorem?, e.g. http://en.wikipedia.org/wiki/Prime_number_theorem.