主要内容
课程: 计算机科学理论 > 单元 2
课程 6: 素性测试试除法
定义问题
我们需要制造一个机器，要能回答一个简单的是否问题。给定一个输入 n，n 是否是质数？
让我们想一想这个机器中需要什么才能工作。机器只能根据 一些指令 按顺序进行一定的步骤，这就称为 演算法。为了热身，让我们看看你大脑里的演算法是什么。 回答这个问题：49 是质数吗？
…
不是？你这是怎样做的？你可能是在 寻找 49 的一个因子，它必须是 大于 1 并小于 49 。如果你没有背熟乘法口诀表，你自然会按照这个顺序做：
- 49 能被 2 整除吗? 不能
- 49 能被 3 整除吗？ 不能
- 49 能被 4 整除吗? 不能
- 49 能被 5 整除吗？ 不能
- 49 能被 6 整除吗？ 不能
- 49 能被 7 整除吗？ 能
我们找到了 49 的因子 (7)，这就 证明了 49 是合数。
建一堵墙
但是，如果我问你 2971215073 是否是质数 呢？
你还在测试吗？在做了几千次测试之后，我还没有找到因子。关键的问题是，什么时候我们才能停止测试并证明 n 是质数？ (让我们把这个称为 “墙”)。作为出发点， 我们的墙要等于 n-1 (因为 n 可被 n 整除)。如果我测试到 2971215072 ，我们要么 能找到因子 (这就证明 n 是 合数) ，要么不能 (这就证明 n 是质数)。
建一堵更好的墙
这样会得到答案，但是我们能不能 移动这个墙并节约一些时间? 要记得，我们在寻找 第一个 (或者最小的) 因子。有时候最小的因子会是 2，但是也可能大得多。这就引起关键的问题：最小的因子能有多大？
已知，任何合整数 n 是由两个或多个质数的乘积组成的 n= P * P …
P 最大的时候 就是 n 有 正好两个因子 的时候，因子是 相等的. 这就称为 平方数，例如 9 (9 = 33) 或 49 (49 = 77)。为了面对这个最差的情况，我们只要把墙修在 n 的平方根的地方！
说服你自己： 如果我们在测试到 n 的平方根以后没有找到 n 的因子，n 一定是质数。试着自己证明这个 (此文章下面有一个推导证明)
测试除法算法
到此为止，我们可以继续了。首先让我们用简单的语言总结这个算法:
- 输入一个整数 n
- 对在 {2 ... sqrt(n)} 之间的每一个整数 x，测试 n 是否能被 x 整除
- 如果你找到了因子， n 就是合数，要不然 n 就是质数
如果你有编程经验，你应该打开一个 CS 草稿 并试着让这个函数能工作。否则的话，你可以进行下一步，在那里我提供了一个 成功的运算，以作为你的初始点。 (是 可以 不用任何编程并完成这个课程）。