High Level Idea
Suppose that $j > i$. Let $k = 4.4 \log n$. Then we need to prove that there is a prime number $p < k$ that doesn't divide $j -i$. Assume to the contrary that this is not the case. Then all primes between $2$ and $k$ divide $j -i$. Since all of them are coprime, the product of all primes between $2$ and $k$ divides $j-i$. In particular, we get $\prod_{\substack{2\leq p \leq k\\p\text{ is prime}}}p \leq j -i \leq n.$ The product in the LHS is sometimes called “primorial” (see http://en.wikipedia.org/wiki/Primorial ). It is known that it roughly equals $e^k$ and therefore is greater than $n$. We get a contradiction.
An Estimate for the Primorial
Let me informally explain why the primorial of $k$ is approximately $e^k$. The factorial of $k$ is approximately $e^{k\ln k}$. In the factorial we multiply all numbers between 1 and $k$, but in the primorial only primes. The density of primes is $1/\ln k$. Therefore, the primorial is approximately $\left(e^{k\ln k}\right)^{1/\ln k} = e^k$.
Numerical Bounds
Note that this proof implies that for large enough $n$ there is a prime number as desired between $1$ and $(1+ o(1))\ln n$. However, for small $n$ the term $o(1)$ may be relatively large. I computed the value of the primorial numerically in PARI/GP for $k\in{2,\dots, 100000}$ and got that the primorial of $k$ is always at least $\exp(\frac{\ln 2}{2} k)$ (the equality is attained for $k=2$). If this is indeed true for all $k$, as my computation suggests, then there is a desired prime between $1$ and $2\, \log_2 n$.