m (Created page with "{{exstart}} Find the largest prime below 1,000,000,000 <div class="mw-collapsible" mw-collapsed data-expandtext="Answer" data-collapsetext="Solution"; overflow:auto;"> Answer:...") |
m |
||
| (5 intermediate revisions by one user not shown) | |||
| Line 1: | Line 1: | ||
{{exstart}} | {{exstart}} | ||
| − | Find the largest prime below | + | 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)$. |
| − | + | {{anstart}} | |
| − | Answer: This is 999,999,937 | + | 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$. |
| − | + | {{anstop}} | |
{{exstop}} | {{exstop}} | ||
| + | |||
| + | 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? | ||
| + | |||
| + | <ul class="mw-collapsible mw-collapsed" data-collapsetext="I understand" data-expandtext="Click here for more information"> | ||
| + | <li>Table is collapsed by default</li> | ||
| + | <li>Second row contains collapsible list</li> | ||
| + | <li>Third row contains a collapsible block with custom labels</li> | ||
| + | </ul> | ||
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?