素数 vs 合数

概述

素数（Prime）和合数（Composite）是大于 1 的正整数的两种互斥分类。素数恰好有 2 个正因数（1 和自身），合数有超过 2 个正因数。整数 1 既不是素数也不是合数。素数是数论的”原子”——每个大于 1 的整数都可以唯一分解为素数的乘积（算术基本定理）。

定义

素数

大于 1 的正整数 $p$ 如果仅被 1 和 $p$ 整除，则称 $p$ 为素数（prime）。等价判定：$p>1$ 且不存在整数 $a$ 使得 $1<a<p$ 且 $a\mid p$。最小的素数是 2，也是唯一的偶素数。素数有无穷多个（欧几里得反证法）。

合数

大于 1 的正整数如果不是素数，则称为合数（composite）。等价判定：$n>1$ 且存在整数 $a$ 使得 $1<a<n$ 且 $a\mid n$。最小的合数是 4。合数 $n$ 必有不超过 $\sqrt{n}$ 的素因子（试除法的基础）。

对比维度

维度	素数	合数
正因数个数	恰好 2 个（1 和自身）	超过 2 个
定义	仅被 1 和自身整除	存在 $1<a<n$ 使得 $a\mid n$
因数上界	无（只有 1 和自身）	必有不超过 $\sqrt{n}$ 的素因子
数量	无穷多个（欧几里得证明）	无穷多个
分布	$\pi (x)\sim x/\ln x$（素数定理）	密度趋近于 1
判定算法	试除法 $O(\sqrt{n})$、Miller-Rabin、AKS	找到一个真因子即可
分解	不可再分（数论的”原子”）	可分解为素数之积
密码学角色	RSA 安全性基础	大合数的因子分解是困难问题
最小值	2（唯一的偶素数）	4

关键区别

• 素数恰好有 2 个正因数，合数有 3 个或更多正因数——因数个数是根本区别
• 素数不可再分，是整数分解的终点；合数可以继续分解为更小的因数
• 素数在正整数中的密度递减（约 $1/\ln n$），合数的密度递增（趋近于 1）
• 2 是唯一的偶素数，所有其他偶数都是合数；所有大于 2 的素数都是奇数
• 判定素数有多项式时间算法（AKS），但将合数分解为素因子没有已知的多项式时间算法

联系

• 素数和合数共同覆盖所有大于 1 的正整数（互斥且完备的分类）
• 每个合数都可以唯一分解为素数的乘积（算术基本定理）
• 素数判定和合数分解在计算复杂性上存在不对称性——这是 RSA 密码系统安全性的基础
• 整除关系是区分素数和合数的基本工具：$a\mid n$ 且 $1<a<n$ 则 $n$ 为合数
• 埃拉托斯特尼筛法通过标记合数（素数的倍数）来找出所有素数

参见

• 素数 — 素数的完整概念卡片
• 整除 — 整除是区分素数和合数的基础