Find the largest prime below $10^9$ and which number is it in the list of primes?Which one is next? Compare to the prime-counting function $\pi(x)$ that counts how many primes are there below $x$ and which Gauss approximated to $x/\ln(x)$.
Answer: This is $999\,999\,937$, the $50\,847\,534$th prime number, for which the prime-counting function $\pi(x)$ compares to Gauss' approximation $\pi(x)\approx x/\ln x=48\,254\,942$ to withing 5% accuracy. The next prime is $1\,000\,000\,007$.
The improvement from Euclid's method to the gcd makes the algorithm require a number of steps which is at most five times the number of digits (in base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 and marks the beginning of computational complexity theory.
well, more things today?