查看“︁试除法”︁的源代码

[[分类:整除理论]]
[[分类:数论算法]]
{{InfoBox
|name=试除法
|eng_name=trial division
}}
'''试除法'''('''trial division''')是质数测试/素性检验算法中最朴素的一种，用于测试一个数是否是[[质数]]，也用于进行整数分解。是一种[[暴力算法]]。

== 定理 ==

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

== 算法 ==

=== 已知质数 ===

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

==== 伪代码 ====

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

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

返回 不是
</syntaxhighlight>

流

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

==== 复杂度 ====

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

{{复杂度|<math>1</math>|<math>\Theta(1)</math>|是1或偶数|<math>\sim \pi(\sqrt{n}) \sim \frac{2\sqrt{n}}{\log n}</math>|<math>\Theta\left(\frac{\sqrt{n}}{\log n}\right)</math>|合数||<math>O\left(\frac{\sqrt{n}}{\log n}\right)</math><ref name='complexity'>https://cs.stackexchange.com/a/50340</ref>}}

=== 简易版 ===

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

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

==== 伪代码 ====

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

令 k ← 2

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

返回 不是
</syntaxhighlight>

流

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

==== 复杂度 ====

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

{{复杂度|<math>1</math>|<math>\Theta(1)</math>|是1或偶数|<math>\sim\sqrt{n}</math>|<math>\Theta(\sqrt{n})</math>|合数||<math>O\left(\frac{\sqrt{n}}{\log n}\right)</math><ref name='complexity'/>}}


{{整除与质数}}