试除法

试除法
术语名称	试除法
英语名称	trial division

试除法(trial division)是质数测试/素性检验算法中最朴素的一种，用于测试一个数是否是质数，也用于进行整数分解。是一种暴力算法。

定理

对正整数 [math]\displaystyle{ n }[/math] ，若 [math]\displaystyle{ n }[/math] 不能被任意不超过 [math]\displaystyle{ \sqrt{a} }[/math] 的质数整除，则其一定是质数。

算法

已知质数

条件：已知一些较小的数是否是质数，可以覆盖这个范围，但由于被判定数较大无法直接进行查找。

伪代码

过程 试除法带小素数表
别名 trial_division_with_prime_list
参数 primes : 正整数 序列 :: 已知的小质数序列
参数 n      : 正整数      :: 被测试的数
返回        : 真假值      :: n是否是质数

循环 k ← 1
当 k ≤ √n 时 // 也用 k² ≤ n
执行
    如果 k | n 那么
        返回 是
    令 k ← primes 中的下一个
继续循环 k

返回 不是

流

质数序列(primes)
.取值当(k ↦ k ≤ √n)
.全部满足(k ↦ k | n)

复杂度

假设任意给定一个数 [math]\displaystyle{ n }[/math] ，是质数的概率相当于随机从 [math]\displaystyle{ [1,n] }[/math] 抽取一个数是质数的概率。

情况	复杂度估计	渐近级别	发生条件
平均情况		[math]\displaystyle{ O\left(\frac{\sqrt{n}}{\log n}\right) }[/math]	-
最好情况	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ \Theta(1) }[/math]	是1或偶数
最坏情况	[math]\displaystyle{ \sim \pi(\sqrt{n}) \sim \frac{2\sqrt{n}}{\log n} }[/math]	[math]\displaystyle{ \Theta\left(\frac{\sqrt{n}}{\log n}\right) }[/math]	合数

简易版

条件：并未记录其他数是否是质数，需要遍历候选范围内的全部整数。

逐一测试给定整数能否被 [math]\displaystyle{ [2, \sqrt{a}] }[/math] 区间内的整数整除。

伪代码

过程 试除法
别名 trial_division
参数 n : 正整数 // 被测试的数
返回 : 真假值 // n是否是质数

令 k ← 2

循环 k
当 k ≤ √n 时执行
    如果 k | n 那么
        返回 是
    令 k ← k + 1
继续循环 k

返回 不是

流

整数序列(闭区间 2 到 √n))
.全部满足(k ↦ k | n)

复杂度

假设任意给定一个数 [math]\displaystyle{ n }[/math] ，是质数的概率相当于随机从 [math]\displaystyle{ [1,n] }[/math] 抽取一个数是质数的概率。

情况	复杂度估计	渐近级别	发生条件
平均情况		[math]\displaystyle{ O\left(\frac{\sqrt{n}}{\log n}\right) }[/math]	-
最好情况	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ \Theta(1) }[/math]	是1或偶数
最坏情况	[math]\displaystyle{ \sim\sqrt{n} }[/math]	[math]\displaystyle{ \Theta(\sqrt{n}) }[/math]	合数

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
	互质
算术基本定理	算术基本定理	标准质因数分解