初等数论入门 Lesson 2 算术基本定理与素数分布初步

算术基本定理

Fundamental Theorem of Arithmetic

$$n=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$$

欧几里得证明素数有无穷多个

我们使用欧几里得证明，使用反证法：

不妨设素数只有有限个，记为：

$$p_1,p_2,\dots,p_n$$

令

$$N=p_1p_2\dots p_n+1$$

由算术基本定理，$N>1$，则必然存一个 $p_i|N$

但 $N\equiv1\pmod {p_i}$，矛盾。

证毕。

筛法

埃氏筛

对素数 $p$，从 $p^2,p(p+1),p(p+2)\dots$ 开始筛

欧拉筛 / 线性筛

维护 primes[]，对于每个 $i$

• 标记 $i\times p$ 为合数
• 若 $p\mid i$，则停止
• 若始终未停止，则加入 primes[] 中

素数计数函数的初等估计

记：

$$\pi(x) = \#\{ p \leq x \mid p \text{ 为素数} \}$$

即不超过 $x$ 的素数个数

切比雪夫不等式有：

当 $x\to +\infty$ 时

$$c_1\dfrac x {\ln x}<\pi(x)<c_2\dfrac x {\ln x}$$

其中 $c_1\approx 0.92$，$c_2\approx 1.11$

故，我们可以认为：

$$\pi(x)\sim \dfrac x {\ln x}$$

这有助于我们快速进行素数的数量级估计。