要检查一个数是否为素数，最简单的方法是尝试将数除以 2 到 n，如果任何运算得到余数为 0，则我们说给定的数不是素数。但是最好只在 n/2 之前进行划分和检查（我知道更好的方法是直到 sqrt(n) ），我想知道跳过后半部分的原因。
假设我们是否需要检查数字 11 是否为质数，11/2 = 5。如果我们在这两种情况下都执行 11/6 或 11/7 或 11/8 或 11/9 或 11/10，我们得到的余数为0. 对于任何给定的数字 n 也是如此。
这就是避免下半场的原因吗？“如果你将给定的数字除以任何大于给定数字一半的数字，余数永远不会为 0 或者换句话说，任何大于给定数字一半的数字都不能整除给定数字”
请帮助我知道是否正确
小智 10
因为，不会使它成为质数的最小倍数是 2。如果您检查了从 0 到 n/2 的所有数字，剩下的可能有效的倍数是多少？如果 2 的倍数大于 n，那么 3 或 4 等的倍数也将大于 n。
所以任何数 N 的最大因数必须 <= N/2
所以是的，取 N/2，并检查所有小于或等于 N/2 的整数。因此，对于 11，您将检查所有小于 5.5 的整数，即 1、2、3、4 和 5。
这里解释了平方根： 为什么我们要检查一个素数的平方根来确定它是否是素数？
而且这个问题之前也有人问过。
要因式分解n您必须除以两个其他整数的数字，请将它们称为a和b。这两个数字都必须是 2 或更大，因此检查大于 的数字没有任何意义n/2，它们不可能被平均划分。
是的， sqrt(n) 更有效，因为如果a大于 sqrt(n) 则b必须更小，并且您已经检查过它。