找质数有什么诀窍

发布网友发布时间：2023-09-03 10:44

共1个回答

热心网友时间：2024-12-14 02:14

根据素数的定义思考。素数是大于1的自然数，除了1和自身外，其他数都不是它的因子。
那我们就可以用一个循环，从2开始遍历到这个数减去1，如果这个数都不能被整除，那么这个数就是素数。

也就是说：
给定一个数 n , i 从 2 开始取值，直到 n - 1(取整数),如果 n % i != 0 , n 就是素数。
进一步思考，有必要遍历到 n - 1 。
除了1以外，任何合数最小的因子就是2，那最大的因子就是 n/2。
那我们就遍历到 n/2就足够了。

如果一个数不能整除比它小的任何素数，那么这个数就是素数。

这种“打印”素数表的方法效率很低，不推荐使用，可以学习思想。

我们的想法是，创建一个比范围上限大1的数组，我们只关注下标为 1 ~ N（要求的上限）的数组元素与数组下标（一一对应）。
将数组初始化为1。然后用for循环，遍历范围为：【2 ~ sqrt(N)】。如果数组元素为1，则说明这个数组元素的下标所对应的数是素数。
随后我们将这个下标（除1以外）的整数倍所对应的数组元素全部置为0，也就是判断其为非素数。
这样，我们就知道了范围内（1 ~ 范围上限N）所有数是素数（下标对应的数组元素值为1）或不是素数（下标对应的数组元素值为0）