P201: Determine whether a given integer number is prime

测试一个整数是否为质数。

质数（Prime number），也称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是质数，则称之为合数（也称为合成数）。^{wiki-prime_number}

照例先写测试用例：

确认一个数n是否为质数有许多种方法。最基本的程序为试除法，但因为速率很慢，没有什么实际用处。有一类现代的质数测试可适用于任意数字上，另有一类更有效率的测试方法，则只能适用于特定的数字之上。大多数此类方法只能辩别n是否为质数。也能给出n的一个（或全部）质因数之程序称为因数分解演算法。^{wiki-prime_number}

试除法

测试n是否为质数的量基本方法为试除法。此一程序将n除以每个大于1且小于等于n的平方根之整数m。若存在一个相除为整数的结果，则n不是质数；反之则是个质数。实际上，若$n = ab$是个合数（其中$a$与$b \ne 1$），则其中一个因数a或b必定至大为$\sqrt{n}$。例如，对$n=37$使用试除法，将37除以$m=2,3,4,5,6$，没有一个数能整除37，因此37为质数。此一程序若能知道直至$\sqrt{n}$的所有质数列表，因为试除法只检查m为质数的状况，所以会更有效率。例如，为检查37是否为质数，只有3个相除是必要的（$m=2,3,5$），因为4与6为合数。 作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的因数数量会随着n的增加而迅速增加。依据下文所述之质数定理，小于$\sqrt{n}$的质数之数量约为$\frac{\sqrt{n}}{ln\sqrt{n}}$，因此使用试除法测试n是否为质数时赗大约会需要用到这么多的数字。对$n=10^{20}$，此一数值约为4.5亿，对许多实际应用而言都太过庞大。^{wiki-prime_number}

我们就使用「没有什么实际用处」的试除法。代码实现：

Python标准库中提供了math模组，其提供了大量数学工具，包括求平方根math.sqrt和向下取整math.floor。

参考文献

^{wiki-prime_number}. https://zh.wikipedia.org/wiki/质数 ↩