algorithm - 找到一个数是质数，为什么检查直到 n/2 更好。在 n 的后半部分避免数字的原因是什么

Question

要检查一个数是否为质数，最简单的方法是尝试将该数除以 2 到 n，如果任何运算的余数为 0，则我们说给定数不是质数。但是最好只划分和检查直到 n/2 (我知道更好的方法是直到 sqrt(n) )，我想知道跳过下半部分的原因。

如果我们需要检查数字 11 是否为素数，11/2 = 5。如果我们在这两种情况下都做 11/6 或 11/7 或 11/8 或 11/9 或 11/10，我们得到的余数为 0。对于任何给定的数字 n 也是如此。

这就是避免下半场的原因吗？ "如果你用给定数除以任何大于给定数一半的数，余数永远不会为 0 或者换句话说，任何大于给定数一半的数都不能整除给定数"

请帮我看看是否正确

Answer 1

因为，不会使它成为质数的最小倍数是 2。如果你已经检查了从 0 到 n/2 的所有数字，剩下多少倍数可能有效？如果 2 的倍数大于 n，则 3 或 4 等的倍数也将大于 n。

所以任何数 N 的最大因数必须是 <= N/2

所以是的，取 N/2，并检查所有小于或等于 N/2 的整数。因此，对于 11，您将检查所有小于 5.5 的整数，即 1、2、3、4 和 5。

这里解释平方根: Why do we check up to the square root of a prime number to determine if it is prime?

这个问题之前有人问过。