Question

判断一个数是否为素数的算法

Answer 1

我们要判断素数，首先要知道素数的定义。

素数：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数;否则称为合数。

知道了素数的定义，那么我们应该想一下，如何去判断一个数是否为素数？

一种思路是，我们在每次得到一个数后，都去计算，去尝试因式分解它，看它除了1和自身之外还有没有其他因子
另一种是，我们去查阅素数表，看这个数在不在素数表上。那我们就要先得到素数表。

1-1:稍微动动脑

思想：
根据素数的定义思考。素数是大于1的自然数，除了1和自身外，其他数都不是它的因子。
那我们就可以用一个循环，从2开始遍历到这个数减去1，如果这个数都不能被整除，那么这个数就是素数。
也就是说：
给定一个数 n , i 从 2 开始取值，直到 n - 1(取整数),如果 n % i != 0 , n 就是素数
进一步思考，有必要遍历到 n - 1 吗？
除了1以外，任何合数最小的因子就是2，那最大的因子就是 n/2
那我们就遍历到 n/2就足够了

这样我们就可以写出这个算法的核心代码：