Greatest possible number of primes between 1 and $x$

Question

Background: I'm making a program in java to calculate all the primes between 1 and any given number ($\pi(x)$). I want to create an array that will contain all the numbers, but resizing an array takes time. The solution I came up with was to initialize the array with more possible elements than I know I will need. The problem with that is that I don't know the greatest possible number of elements I will need.

This page show how to approximate $\pi(x)$ with $\frac{x}{\log x - 1}$, but I want to find a fairly simple function such that $f(x)$ is always $\ge \pi(x)$. I considered using something similar to $1.1(\frac{x}{\log x - 1})$, but there is a possibility that $\pi(x) - \frac{x}{\log x - 1}$ increases exponentially.

Does anybody know of an equation for $f(x)$ so that for every value of $x$, $f(x)$ is greater than—but still as close as possible to—$\pi(x)$?

How are we defining "close to"? – Dennis Meng Jan 27 '14 at 17:14 — Dennis Meng, Jan 27 '14 at 17:14
@DennisMeng edited to "as close as possible to" – The Guy with The Hat Jan 27 '14 at 17:15 — The Guy with The Hat, Jan 27 '14 at 17:15

score 1 · Accepted Answer · answered Jan 27 '14 at 17:15

1

On the page you linked to, you find a result by Dusart that for all $x>1$ $$ \pi(x) <\frac x{\ln x}\cdot\left(1 + \frac{1.2762}{\ln x}\right) $$ Sine also $\pi(x)>\frac{x}{\ln x}$ this bound is close to $\pi(x)$ in the sense that the relative error tends to $0$ as $x$ gets large.

answered Jan 27 '14 at 17:15

Hagen von Eitzen

374,180

Ah, thanks. I saw if x>598 but didn't see (The upper bound holds for all x > 1.). Silly me, and thanks again! – The Guy with The Hat Jan 27 '14 at 17:21

Greatest possible number of primes between 1 and $x$

1 Answers1