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

{{noteTA|G1=Math}}
'''试除法'''是[[整数分解]]演算法中最简单和最容易理解的演算法。首次出現於[[義大利]]數學家[[費波那契]]出版於1202年的著作。

给定一个待分解的正整數''n''，试除法是用小于等于<math>\sqrt{n}</math>的每个[[素数]]<ref>{{cite web|url = https://primes.utm.edu/glossary/page.php?sort=TrialDivision|quote=just divide by all the primes less than (or equal to) its square root.|title = trial division|website = The PrimePages|archive-url=https://web.archive.org/web/20230212123405/https://primes.utm.edu/glossary/page.php?sort=TrialDivision|archive-date=2023-02-12|access-date=2023-02-12|author = Chris K. Caldwell|language = en}}</ref><ref>{{Planetmath reference|urlname = trialdivision|title = Trial division|quote = where a given integer <math>n</math> is tested for divisibility by each prime <math>p_i</math> in order until all its factors are discovered|access-date = 2023-02-12|language = en}}</ref>去试除。如果找到一个数能够整除除尽，这个数就是可分解整数的因數。若''n''為合數，則试除法一定能够找到''n''的質因數，因為''n''最小的質因數不大於其平方根，所以如果这个演算法“失败”，也就证明了''n''是个素数。

某种意义上说，试除法是个效率非常低的演算法，如果从2开始，一直算到<math>\sqrt{n}</math>需要
<math>\pi(\sqrt{n})</math>次试除，这里<math>\pi(x)</math>是[[素数计数函数|小于x的素数的个数]]。这是不包括[[素性测试]]的。如果稍做变通——还是不包括素性测试——用小于<math>\sqrt{n}</math>的奇数去简单的试除，则需要<math>{\sqrt{n}\over 2}</math>次。这意味着，如果''n''有大小接近的素因數（例如[[公钥密码学]]中用到的），试除法是不太可能实行的。但是，当''n''有至少一个小因數，试除法可以很快找到这个小因數。值得注意的是，对于随机的''n''，2是其因數的[[概率]]是50％，3是33％，等等，88％的正整数有小于100的因數，91％的正整数有小于1000的因數。

==参见==
*[[卢卡斯-莱默检验法]]
*[[埃拉托斯特尼筛法]]
*[[米勒-拉宾检验]]
*[[费马素性检验]]

== 參考文獻 ==
{{reflist}}

[[Category:素性测试]]
[[Category:除法]]
[[Category:整数分解算法]]