There are at least $n$ primes between $n$ and $n^2$

Theorem 1: $\pi(2^k) \le 3\dfrac{2^k}{k}$

(1)  For $k \le 5$:

$\pi(2^1) = 1 \le 2\dfrac{2^1}{1} = 4$
$\pi(2^2)  = 2 \le 2\dfrac{ 2^2}{2} = 4$
$\pi(2^3) = 4 \le 2\dfrac{2^3}{3} = \dfrac{16}{3} > 5$
$\pi(2^4) = 6 \le 2\dfrac{2^4}{4} = 8$
$\pi(2^5) = 11 \le 2\dfrac{2^5}{5} = \dfrac{64}{5} > 12$

(2)  Assume it is true up to some $k \ge 5$

(3) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$ since:

(a) $2^{2n} = \sum\limits_{i \le 2n}{{2n}\choose i}$

(b) $n^{\pi(2n) - \pi(n)} \le p^{\pi(2n) - \pi(n)} \le \prod\limits_{n < p \le2n}p \le {{2n}\choose{n}} \le 2^{2n}$

(c) $(\pi(2n) - \pi(n))\log n \le (2n)\log 2$

(d) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$

(4) $\pi(2^{k+1}) - \pi(2^k) \le (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$ so that $\pi(2^{k+1}) \le \pi(2^k) + (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$

(5)  $\log 2^{k} = k\log 2$ so that $\dfrac{1}{k} = \dfrac{\log 2}{\log 2^{k}}$

(6)  $5k+5 < 6k$ so that $\dfrac{5}{k} < \dfrac{6}{k+1}$

(7)  $\pi(2^{k+1}) \le \pi(2^k) + \dfrac{2^{k+1}}{k} \le \dfrac{3\times2^k}{k} + \dfrac{2\times2^k}{k} = \dfrac{5\times2^k}{k} \le \dfrac{3\times2^{k+1}}{k+1}$


Corollary: $\pi(x) \le 6 \log 2 \dfrac{x}{\log x}$

(1)  For $x \le 4, \pi(x) \le 6\log 2 \dfrac{x}{\log x}$

$\pi(2) = 1 \le 6\log2\dfrac{2}{\log 2}$ since $\log 2 < 12\log 2$

$\pi(3) = 2 \le 6\log 2\dfrac{3}{\log 3}$ since $2\log 3 < 18\log 2$

$\pi(4) = 2 \le 6\log 2\dfrac{4}{\log 4}$ since $2\log 4 < 24\log 2$

(2)  There exists $k$ such that $2^k \le x \le 2^{k+1}$

(3)  $\dfrac{1}{k+1} < \dfrac{\log 2}{\log 2^{k}}$ since $\log 2^k < (k+1)(\log 2)$

(4)  $\pi(x) \le \pi(2^{k+1}) \le 3\dfrac{2^{k+1}}{k+1} \le 6\dfrac{2^{k}}{k+1} < 6\log 2\dfrac{2^k}{\log 2^k} \le 6\log 2\dfrac{x}{\log x}$

Let $v_p(n)$ be the maximum power of $p$ that divides $n$

Lemma 1: $v_p(n!) = \sum\limits_{m \ge 1}\left\lfloor\dfrac{n}{p^m}\right\rfloor$

There are $\left\lfloor\dfrac{n!}{p}\right\rfloor$ instances of numbers divisible by $p$.

There are $\left\lfloor\dfrac{n!}{p^2}\right\rfloor$ instances of numbers divisible by $p^2$

And so on.

Lemma 2: $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor \in \{0, 1\}$

(1)  Let $\{x\}$ be the fractional part of $x$

(2)  If $\{x\} < \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 0$

(3)  If $\{x\} \ge \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 1$

Theorem 2: $\pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$

(1) If $m > \dfrac{\log 2n}{\log p}$, then $\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor = 0$

(2)  $v_p\left({{2n}\choose{n}}\right) = \sum\limits_{m \ge 1}\left(\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor\right) \le \left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor$

(3)  $\dfrac{2^{2n}}{2n} \le {{2n}\choose{n}}$

(4) $2n\log 2 - \log 2n \le \log {{2n}\choose{n}} \le \sum\limits_{p \le 2n}\left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor\log p \le \sum\limits_{p \le 2n}\log 2n = \pi(2n)\log 2n$

(5) $\pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1$

(6)  For $2 \le x \le 16, \pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$

• $\pi(2) = 1 = \dfrac{\log 2}{2}\dfrac{2}{\log 2} = 1$
• $\pi(3) = 2  > \dfrac{3}{2} > \dfrac{\log 2}{2}\dfrac{3}{\log 3}$
• $\pi(4) = 2 =  \dfrac{4}{2} > \dfrac{\log 2}{2}\dfrac{4}{\log 4}$
• $\pi(5) = 3 \ge \dfrac{5}{2} > \dfrac{\log 2}{2}\dfrac{5}{\log 5}$
• $\pi(6) = 3 = \dfrac{6}{2} > \dfrac{\log 2}{2}\dfrac{6}{\log 6}$
• $\pi(7) = 4 > \dfrac{7}{2} > \dfrac{\log 2}{2}\dfrac{7}{\log 7}$
• $\pi(8) = 4 = \dfrac{8}{2} > \dfrac{\log 2}{2}\dfrac{8}{\log 8}$
• $\pi(9) = 4  > \dfrac{3}{2} = \dfrac{\log 2}{3\log 2}\dfrac{9}{2} > \dfrac{\log 2}{2}\dfrac{9}{\log 9}$
• $\pi(10) =4 > \dfrac{5}{3} = \dfrac{\log 2}{3\log 2}\dfrac{10}{2} > \dfrac{\log 2}{2}\dfrac{10}{\log 10}$
• $\pi(11)=5 > \dfrac{11}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{11}{2} > \dfrac{\log 2}{2}\dfrac{11}{\log 11}$
• $\pi(12)=5 > 2 = \dfrac{\log 2}{3 \log 2}\dfrac{12}{2} > \dfrac{\log 2}{2}\dfrac{12}{\log 12}$
• $\pi(13)=6 > \dfrac{13}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{13}{2} > \dfrac{\log 2}{2}\dfrac{13}{\log 13}$
• $\pi(14)=6 > \dfrac{7}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{14}{2} > \dfrac{\log 2}{2}\dfrac{14}{\log 14}$
• $\pi(15)=6 > \dfrac{5}{2} = \dfrac{\log 2}{3 \log 2}\dfrac{15}{2} > \dfrac{\log 2}{2}\dfrac{15}{\log 15}$
• $\pi(16)=6 > \dfrac{8}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{16}{2} > \dfrac{\log 2}{2}\dfrac{16}{\log 16}$

(7)  There exists $n$ such that $16 \le 2n < x \le 2n+2$

(8)  $\dfrac{2n}{\log 2n} - \dfrac{n+1}{\log 2n} = \dfrac{n-1}{\log 2n} \ge \dfrac{7}{\log 16} = \dfrac{7}{4\log 2} > \dfrac{4}{4\log 2} = \dfrac{1}{\log 2}$

(9) $\pi(x) \ge \pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1 = \dfrac{2n\log 2 - \log 2n}{\log 2n} = \dfrac{\log\frac{2^{2n}}{2n}}{\log 2n}$

(10) for $n=8$, $2^6 > 8$

(11)  $2(2^{n-2}) = 2^{(n+1)-2} > 2n > n+1$ so that $\dfrac{2^{n-2}}{n} > 1$ and $\dfrac{2^{n-1}}{2n} > 1$ and $\dfrac{2^{2n}}{2n} > 2^{n+1}$

(12)  $\dfrac{\log\frac{2^{2n}}{2n}}{\log 2n} \ge \dfrac{\log 2^{n+1}}{\log (2n+2)} = \dfrac{(n+1)\log 2}{\log (2n+2)}$

(13)  Since $n+1 = \dfrac{2n+2}{2} \ge \dfrac{x}{2}$, it follows that $\dfrac{(n+1)\log 2}{\log (2n+2)} \ge \dfrac{x\log 2}{2\log x}$

Corollary: For $46 \ge n \ge 4$, there are at least $n$ primes between $n$ and $n^2$

(1)  For $n \ge 28$, then:

• Between $4$ and $16$, there are 4 primes: $\{5, 7, 11, 13\}$
• Between $5$ and $25$, there are 6 primes: $\{7,11,13,17,19,23\}$
• Between $6$ and $36$, there are more than $6$ primes: $\{7,11,13,17,19,23,\dots\}$
• Between $7$ and $49$, there are more than $7$ primes: $\{11,13, 17, 19, 23, 29, 31,\dots\}$
• Between $8$ and $64$, there are more than $8$ primes: $\{11, 13,17,19,23,29,31,37,\dots\}$
• Between $9$ and $81$, there are more than $9$ primes: $\{11,13,17,19,23,29,31,37,41,\dots\}$
• Between $10$ and $100$, there are more than $10$ primes: $\{11,13,17,19,23,29,31,37,41,43,dotts\}$
• Between $11$ and $121$, there are more than $11$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,\dots\}$
• Between $12$ and $144$, there are more than $12$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,59,\dots\}$
• Between $13$ and $169$, there are more than $13$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,\dots\}$
• Between $14$ and $196$, there are more than $14$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,\dots\}$
• Between $15$ and $225$, there are more than $15$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,\dots\}$
• Between $16$ and $256$, there are more than $16$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,\dots\}$
• Between $17$ and $289$, there are more than $17$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,\dots\}$
• Between $18$ and $324$, there are more than $18$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,\dots\}$
• Between $19$ and $361$, there are more than $19$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,\dots\}$
• Between $20$ and $400$, there are more than $20$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,\dots\}$
• Between $21$ and $441$, there are more than $21$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,\dots\}$
• Between $22$ and $484$, there are more than $22$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113\dots\}$
• Between $23$ and $529$, there are more than $23$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,\dots\}$
• Between $24$ and $576$, there are more than $24$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,\dots\}$
• Between $25$ and $625$, there are more than $25$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,\dots\}$
• Betwen $26$ and $676$, there are more than $26$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,\dots\}$
• Between $27$ and $729$, there are more than $27$ primes, $\$\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,\dots\}$

(2)  $\pi(n^2) - \pi(n) \ge \dfrac{(n^2)\log 2}{2\log (n^2)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(n^2)\log 2}{4\log (n)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(\frac{n}{4} - 6)(n\log 2)}{\log n}$