质数
定义
若一个正整数无法被除了 \(1\) 和它自身之外的任何自然数整除，那么称这个这个正整数为质数，否则称该正整数为合数。
在整个正整数集合中，质数的数量不多，但是无穷无尽的，分布比较稀疏，对于一个足够大的正整数 \(N\) ，不超过 \(N\) 的质数大约有 \(N / \text{In}~N\) 个。即每 \(\text{In}~N\) 个数大约有一个质数分布。
什么是 \(\text{In}~N\) ？它表示的意义是以 自然常数 \(e\) 为底的数，其中 \(e\) 约等于 \(2.71828183...\) ，所以可以把 \(\text{In}~N\) 认为是 \(log_2~N\) 级别的。（ \(log_2~N > \text{In}~N\) ）
质数的判定
试除法
若一个 \(N\) 为合数，则一定存在一个能整除 \(N\) 的正整数 \(T\)，其中 \(2 \le T \le \sqrt{N}\)。
证明
由定义得 \(N\) 为合数，所以存在一个能整除 \(N\) 的正整数 \(M\) ，其中 \(2 \le M \le N-1\)。
反证法，假设命题不成立，那么这样的数 \(M\) 一定满足 \(\sqrt{N}+1 \le M \le N-1\)。因为 \(M\) 能整除 \(N\)，所以它们的商 \(N/M\) 也能整除 \(N\)，而 \(2 \le N/M \le \sqrt{N}\)，令 \(T=N/M\) ，这与假设矛盾，故假设不成立，原命题成立。
根据上述命题，我们只需要扫描 \(2 \to \sqrt{N}\) 之间的所有整数，依次检查它们能否整除 \(N\)，若都不能整除，则 \(N\) 是质数，否则 \(N\) 为合数。试除法的时间复杂度为 \(\mathcal{O}(\sqrt{N})\) 。注意要特判 \(0\) 和 \(1\) 它们既不是质数也不是合数。
\(Code\)
试除法代码模板：
bool isprime(int x)
{
if(x<2)return false;
for(int i=2;i*i<=x;i++)
if(x%i!=0)return false;
return true;
}
“试除法”作为最简单也是最经典的确定性算法，是我们在算法竞赛中常用的方法。有一些效率更高的算法，例如“\(Miller-Robbin\)”等，有较小的概率把合数误判定为质数，但多次判定后合起来的错误概率趋近于零。