这个素数的原理是什么

Question

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

Answer 1

这个程序的素数判断的原理是：对于一个数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是素数。