要检查一个数是否是素数，最简单的方法是尝试将这个数除以 2 到 n，如果任何操作得到余数为 0，那么我们就说给定的数不是素数。
但最好只进行划分和检查直到 n/2 （我知道更好的方法是直到 sqrt(n) ），我想知道跳过后半部分的原因。
假设我们是否需要检查数字 11 是否是素数，
11/2 = 5。
如果我们在这两种情况下都执行 11/6 或 11/7 或 11/8 或 11/9 或 11/10 ，我们得到的余数都是 0。
对于任何给定的数字 n 都是如此。
回避下半场的理由就是这个吗？ “如果你将给定的数字除以任何大于给定数字一半的数字，余数永远不会为 0 或者换句话说，大于给定数字一半的数字都不能整除给定数字”
请帮助我知道我是否正确
因为，不能使其成为质数的最小倍数是 2。如果您检查了从 0 到 n/2 的所有数字，还剩下什么倍数可能有效？如果 2 的倍数大于 n，则 3 或 4 等的倍数也将大于 n。
因此任何数字 N 的最大因数必须
所以是的，取 N/2，并检查所有小于或等于 N/2 的整数。因此，对于 11，您将检查所有小于 5.5 的整数，即 1、2、3、4 和 5。
平方根的解释如下：为什么我们要检查素数的平方根来确定它是否是素数？ https://stackoverflow.com/questions/5811151/why-do-we-check-upto-the-square-root-of-a-prime-number-to-determine-if-it-is-pri
这个问题之前已经被问过。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
