What is the simplest lower bound on prime counting functions proof wise? I am trying to understand how a lower bound can exist on the prime counting function, and to begin this process of educating myself I am trying to find a simple complete proof, that does not hinge on another more complex theory?
 A: Given $k$ primes $p_1,\ldots,p_k$, let us calculate the number of products of these primes below some threshold $2^n$. That is, ask how many choices of exponents $a_i\in \mathbb N$ satisfy:
$$p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}\leq 2^n.$$
Since every prime is at least $2$, we get that this statement implies
$$2^{a_1+a_2+\ldots+a_k}\leq 2^n$$
$$a_1+a_2+\ldots+a_k\leq n.$$
A stars and bars argument establishes that the number of tuples $(a_1,\ldots,a_k)$ satisfying this is ${n+k\choose n}$. There are $2^n$ integers in the interval $[1,2^n]$ and each can be written as a product of primes less than $2^n$. Thus, we must have, setting $k=\pi(2^n)$:
$${n+\pi(2^n)\choose n}\geq 2^n.$$
That's a pretty painless proof.

Okay, let's do the painful bit of showing that this is a logarithmic bound. This is, unfortunately, using harder tools than were required to derive the bound in the first place. It basically reduces to figuring out that there is some $\alpha$ such that the minimal $\pi(2^n)\geq \alpha n$ for large enough $n$. To do so, consider the value $${(\alpha+1)n \choose n}=\frac{((\alpha+1)n)!}{n!(\alpha n)!}$$ where we slightly abuse notation in assuming the relevant terms are integers. Since we're going to use an asymptotic approximation, this does not really matter. Using Stirling's approximation that $n!\sim \sqrt{2\pi n}(n/e)^n$ on every factorial gives
$${(\alpha+1)n \choose n}\sim  \frac{1}{\sqrt{2\pi n}}\cdot \frac{\sqrt{\alpha+1}}{\sqrt{\alpha}}\cdot \frac{((\alpha+1)n/e)^{(\alpha+1)n}}{(n/e)^n(\alpha n/e)^{\alpha n}}=\frac{1}{\sqrt{2\pi n}}\cdot \frac{\sqrt{\alpha+1}}{\sqrt{\alpha}}\cdot \left(\frac{(\alpha+1)^{\alpha+1}}{\alpha^{\alpha}}\right)^n$$
What should be clear is that this function is eventually bounded by $\frac{(\alpha+1)^{\alpha+1}}{\alpha^{\alpha}}$, meaning that expression must be at least two. Numerically, this gives $\alpha\geq .2938\ldots$. For the minimal possible $\alpha$ given by this inequality, we would get
$$\pi(2^n)\geq \alpha n$$
for big enough $n$. This suffices to establish a logarithmic lower bound on the prime counting function.
A: Actually, I absolutely fail to understand why the classical Chebyshev bound is considered to be so difficult. The proof consists of four elementary steps:
1) $A_n={2n \choose n}=\frac{(2n)!}{n!^2}$ is an integer whose factorization includes only primes $p\le 2n$. In addition, this number is fairly large: since $\frac{n+k}{k}\ge 2$ for all $1\le k\le n$, we have $A_n\ge 2^n$.
2) The power of a prime $p$ in $m!$ equals $\left[\frac mp\right]+\left[\frac m{p^2}\right]+\dots+\left[\frac m{p^k}\right]$ where $p^k\le m< p^{k+1}$.  
3) Hence the power of any prime $p$ in $A_n$ equals $\sum_{j=1}^{k_p}\left(\left[\frac {2n}{p^j}\right]-2\left[\frac n{p^j}\right]\right)\le k_p$,
where $p^{k_p}\le 2n< p^{k_p+1}$ (we used here the trivial observation that $[2x]-2[x]\le 1$ for all $x$).
4) Thus, $2^n\le A_n\le \prod_{p\le 2n}p^{k_p}\le (2n)^{\pi(2n)}$ whence 
$$
\pi(2n)\ge \frac{n\log 2}{\log(2n)}
$$
giving you the right order of magnitude at the expense of at most half an hour of studies.
A: Here is an answer that uses the Fundamental Theorem of Arithmetic. Let $\pi(n)$ be the number of primes less than or equal to $n$. For each natural $k$ less than $n$, the exponent of the primes in the prime factorization of $k$ can be at most $\log_2(n)$. 
Since there are $\pi(n)$ total primes that can be used in the prime factorization of $k$, we have 
$$(\log_2(n) + 1)^{\pi(n)} \ge n \implies \pi(n) \ge \frac{\log(n)}{\log(\log_2(n) + 1)} \approx \frac{\log(n)}{\log \log(n)}.$$
Interestingly, exponentiating this bound gives you the PNT. 
A: Here's a very easy to prove lower bound:
Consider the product of all primes less than $n$, call it $P_n$.  Let the largest prime less than $n$ be $q_n$.  There must be a prime on $[q_n+1, P_n+1]$ (this is because $P_n+1$ must itself be prime or be divisible by some other prime, but isn't divisible by any prime less than or equal to $q_n$).  Clearly, $P_n+1\leq n!$ for $n>2,n\in\mathbb{N}$
Given that $\pi(3)=2$, we see that $\pi(3!)=\pi(6)\geq2+1=3$, then $\pi(6!)\geq4$
In general $\pi(3\underbrace{!!...!!}_{n})\geq n+1$
Interpolation is easy, let $\pi(n)=\pi(k)$ for $k=\sup\{3\underbrace{!!...!!}_{m}|3\underbrace{!!...!!}_{m}\leq n\}$
A: There's a simple lower bound due to Erdős which I detailed over in another answer. For completeness, I'll repost the argument as an answer here.

Let $n\in\mathbb{N}=\{1,2,3,\ldots\}.$ Consider the set $$S(n) = \{(k,l)\in\mathbb{N}^{2}:l\text{ is square-free and }k^{2}l\leq n\}.$$ It is a standard fact that every natural number has a unique representation in the form $k^{2}l,$ where $k$ and $l$ are natural numbers and $l$ is square-free. This gives $\lvert S(n)\rvert = n.$
Now if we have a pair $(k,l)$ with $k^{2}l\leq n,$ then  we must have $k^{2}\leq n$ and $l\leq n$, since $k$ and $l$ are positive. Note that this gives $k\leq\sqrt{n}.$ Since $l$ is square-free, $l$ can be expressed as a product of distinct primes, each of which must be not-greater-than $n$ since $l\leq n$. That is, $l$ can be expressed as a product of the primes $p_{1},p_{2},\ldots,p_{\pi(n)}.$ There are $2^{\pi(n)}$ such products.
Therefore, if we know $(k,l)\in S(n)$ then there are at most $\sqrt{n}$ possibilities for what $k$ might be and at most $2^{\pi(n)}$ possibilities for what $l$ might be (independent of $k$, of course). It follows that $\lvert S(n)\rvert \leq 2^{\pi(n)}\sqrt{n},$ so $n\leq2^{\pi(n)}\sqrt{n}.$
Taking $\log$s and rearranging gives the following result: $$\pi(n)\geq\frac{\log{n}}{2\log{2}}\quad\text{for }n=1,2,\ldots.$$

A: According to Bertrand's postulate (proofs of which may be found here), if $n\geq 2$, then there is a prime between $n$ and $2n$ (not including $n$). Therefore, in general, $\pi(2x) \geq \pi(x)+1$. Since $\pi(2)=1$, we have $\pi(4)\geq 1+1=2, \pi(8)\geq 2+1=3$, and in general, $\pi(2^n)\geq n \implies \pi(x) \geq \log_2(x)$ (since $\pi$ is increasing). This lower bound is by no means optimal, but it is simple and admits a relatively simple proof. 
