天才一秒记住【狂风中文网】地址：https://www.kfzw.net
例如，我们来检测18905是否能被17整除：
18905→1865→161→11，
因而它不是17的倍数。
但对于19，整除性测试给出了另一种结论：
18905→1900=100×19。
拥有了这一组测试，你现在就可以检查不大于500的所有数的素性，因为232=529超过了500，因此19是你需要考虑的最大的素因数。
例如，为了确定247的性质，我们只需要检查它是否能被不大于13的素因数整除，因为下一个素数的平方，172=289超过了247。
通过对13的测试，我们发现247→（24＋28）=52→13，这是一个13的倍数（247=19×13）。
素数相乘可以得到无平方因数的数（square-freenumber），要想构造关于这些数的整除性测试，可以叠加并行其素数因子的整除性测试。
比如，对于42=2×3×7，一个数n能被42整除，当且仅当n可以通过2，3和7的三项整除性测试。
但是，对于那些有平方数因数的数，像9=32，则不能由此得到。
顺便说一句，9是n的因数，当且仅当9也是n的各位数字之和的因数。
你也许会问：数千年以来，那些聪明的数学家们难道还没有想出更好、更精妙的检测素性的方法？答案是有的。
2002年，我们发现了一个相对快速的判断一个给定的数是否为素数的方法。
不过，如果给定的数恰好是一个合数，那么这个所谓的“AKS素性测试”
（AKSprimalitytest）并不能给出该数的因数分解。
虽然原则上说找到一个给定数的素因数的问题可以通过试错来解决，但实际操作中，这对于很大的整数依然难以实现。
正因为此，它构成了很多互联网加密方法的基础。
我们会在第4章回到这个话题。
在那之前，我们会在接下来的两章中更近距离地认识一下素数和因数分解。
[1] 这里用中文数字“六”
，强调的是“六”
这个数本身的概念，下同。
—译者注。
如无特殊说明，以下注释均为译者注。
[2] 我国的自然数包含0，而本书所说的自然数不包含0。
[3] 1码=3英尺=36英寸。
[4] 或称因子、约数，英文也可以写作divisor。
[5] 英文也可以写作prime。
[6] 这里指的立方数从2的立方开始，因为1=13。
[7] 又称丰数或过剩数。
[8] 最近的例子是孪生素数猜想，传奇美籍华裔数学家张益唐在2013年取得重大进展，引起轰动。
[9] 又称埃氏筛或素数筛，简称筛法。
埃拉托斯特尼（公元前276——公元前194），古希腊数学家、地理学家。
[10] 当解释有关任意数的性质的时候，数学家们会用符号为讨论的对象赋予名称。
对于数，这些名字通常都是小写字母，如m和n；两个数的积m×n经常简写为mn。
——作者注
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！