这个素数的原理是什么

img


这个求素数的逻辑是什么，我怎么看都看不出来这个逻辑到底怎么弄

这个程序的素数判断的原理是：对于一个数m，如果它不是素数，那么它一定可以被分解成若干质因数的乘积，其中质因数小于等于m的平方根。因此，我们可以用一个循环，从2到m的平方根遍历每个数，如果m可以被其中任意一个数整除，那么m就不是素数，否则m是素数。

举个例子，如果m=25，那么m的平方根为5，在循环中我们只需要判断2,3,4,5是否可以整除25，因为只要有一个质因数就可以把25分解出来。由于25可以被5整除，所以25不是素数。如果m=23，那么在循环中我们依然只需要判断2,3,4,5是否可以整除23，但是这些数都不能整除23，所以23是素数。

对于任何一个数n，它的因子中，除了自身外，最大因子值不会超过n的开根号值。比如16的因子中，除了16之外，最大因子是4
所以判断素数时，没有必要从1比较到15，只需要比较到4就可以结束了

1、对数m开根号 ==> 因为如果m不是素数，他的一个因子一定会 小于 根号m
2、从 2 到 k 循坏对数m取余，如果余数为0，则说明它存在1和自身之外的因子，那么m就不是素数
3、如果循环结束还没有找到m的因子，那么他就是素数