存在无限多个素数，欧几里德递归证明：
$$P_n = P_1P_2\cdots P_{n-1} + 1, (n>=1) $$
前 $n-1个$素数中没有能除尽 $P_n$的，因为都每个能除尽 $P_{n-1}$。
形如：$2^p-1$ （$p$是素数）的数称为Mersenne numbers，中文名为梅森数
如果该梅森数也是素数的话，就叫梅森素数。
如果 $n$是合数，则数 $2^n-1$不可能是素数。
证明为：$2^{km} - 1 = (2^m -1)(2^{m(k-1)} + 2^{m(k-2)} + \cdots + 1)$
但当 $p$是素数时，$2^p -1$不总是素数。
如最小的非梅森数 $2^{11} -1 = 2047 = 23*89$
http://acm.zju.edu.cn/show_problem.php?pid=2400
有个渐近公式，第 $k$个素数$P_k \approx k \ln k$
这意味着当$k\rightarrow \infty , \frac{P_k}{k \ln k} \rightarrow 1$
则类似的可以推出 $\pi (x)$表示不超过 $x$的素数个数，$\pi (x) \approx \frac{x}{\ln k}$
当 $n$或 $x$趋向无穷大时，有更精确的估计函数。
$$ \begin{array}{ll} \ln x - \frac{3}{2} <, \frac{x}{\pi (x))} <, \ln x - \frac{1}{2}, &\text{ for } x>=67; \\ n(\ln n + \ln \ln n -\frac{3}{2}) <, P_n <, n(\ln n + \ln \ln n - \frac{1}{2}), & \text{ for } n>=20; \end{array} $$
最后讲到了Eratoshenes筛法，这个太简单了，也不唠叨了~