找到一个数字是质数，为什么检查到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?

这个问题以前已经被问过了。

Answer 2

要将必须除以另外两个整数的数字进行因式分解，请将它们称为a n b。这两个数字都需要是2或更大，所以检查大于n/2的数字没有任何意义，它们不可能平分。

是的，sqrt(n)更有效，因为如果a大于sqrt(n)，那么b必须小于sqrt(N)，并且您已经检查过了。

Answer 3

目的-证明一个复合数的因子(不包括1和数本身)属于集合{2，3，4，5，6…，n/2}，其中[]表示最大整数函数。

证明：

假设合成数是n，用两个因子a，b的乘积表示(这两个因子都不等于1或n，因为我们确定1和n都会除以n，因此a和b可以是的最小自然数是2)。

 n=a x b

假设a>n/2。

 Then  b=n/a this implies that b<2 

(例如，假设n=39，则a>39/ 2 =19。假设a是20 (大于19)，则b=39/20=1.95，这是不可能的，因为a和b的最小可能值都将是2(根据我们的假设)，因为不满足a=20进一步增加a将使b小于和小于2的条件。同样，可以将思维过程扩展到所有的合成数！)

这是不可能的，因为最小的自然数a和b可能是2。

因此，我们的假设是错误的，因此a和b都属于集合{2，3，4，5，6…，n/2}。