Question

判断素数

Answer 1

素数：又称质数。是大于1自然数中的除了自身和1以外不能别其他数整除的数字。

利用这个素数的定义，我们可以得出第一种判断素数的方法：

这个方法是最简单的判断方法，它使指迟兆用一个for循环来让n一次次的除以小于n的每个数，如果除尽了的话，就不满足素数的定义。
但是这个方法也是计算量最大的。它总共会计算n-2次。

第二种方式是：如果 n 能够被 2 ~ 之间的数整除就不是素数（合数），反之为素数。

所以，根旦团据这个性质我们可以减少判断的次数来节约运算时间。

这个方法比上一个方法减少了很多的时间。所以使用这种方法的时候会更能提高程序的效率。

有人可能会问，这里为什么是 ？
因为一个数 N 的的因数可以分为两部分，一部分是小于 的，唯租另一部分是大于 的。而小于的那部分和大于的一一对应。所以只需要判断 2 ~ 即可。