素数

素数是整数的"原子"，算数基本定理保证每个整数都由素数唯一拼成。

定义

大于 $1$ 的整数 $p$ 称为素数（质数），若它的正因数只有 $1$ 和 $p$ 本身。大于 $1$ 且不是素数的整数称为合数。

性质

• 若 $p$ 为素数且 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$（欧几里得引理）
• 素数有无穷多个。反设仅有 $p_1,\dots,p_r$ 这些素数，则 $N = p_1p_2\cdots p_r + 1$ 不被任何 $p_i$ 整除，故 $N$ 必有新的素因子，矛盾
• 除 $2$ 外，素数均为奇数；相邻素数之间可任意远（对任意 $k$，$(k+1)! + 2,\dots,(k+1)! + (k+1)$ 是 $k$ 个连续合数）

素数判定

• 试除法：若 $n$ 没有不超过 $\sqrt{n}$ 的素因子，则 $n$ 为素数
• 埃拉托斯特尼筛法：列出 $2$ 到 $N$ 的整数，从小到大划去每个素数的倍数，未被划去的即为素数

示例

• $100$ 以内的素数：$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$
• $\sqrt{97} < 10$，用 $2,3,5,7$ 试除均不能整除 $97$，故 $97$ 为素数
• 素数在自然数中越来越稀疏，$\pi(x)$ 约为 $\dfrac{x}{\ln x}$（素数定理，属解析数论，见数论）