为什么我们要检查到素数的平方根以确定它是否是素数？

StackOverflow https://stackoverflow.com/questions/5811151

题

要测试一个数字是否是素数，为什么我们必须测试它是否仅能排除到该数字的平方根？

有帮助吗？

解决方案

如果一个数字 n 不是素数，可以纳入两个因素 a 和 b:

n = a * b

如果两者 a 和 b 大于 n, ， 然后 a * b 将大于 n. 。因此，至少其中一个因素必须小于或等于 n, ，如果我们找不到任何小于或等于平方根的因素， n 必须是素数。

其他提示

假设 m = sqrt(n) 然后 m × m = n. 。现在 n 那不是当时的 n 可以写成 n = a × b, ， 所以 m × m = a × b. 。注意 m 是一个实数，而 n, a 和 b 是自然数。

现在可以有3例：

  1. a>m⇒b<m
  2. a =m⇒b= m
  3. a <m⇒b> m

在所有三种情况下， min(a, b) ≤ m. 。因此，如果我们搜索到 m, ，我们必然会找到至少一个因素 n, ，足以表明 n 不是素数。

因为如果一个因子大于n的平方根，那么将其乘到n等于n的另一个因素必须小于n的平方根。

更直观的解释是： -

100的平方根为10。例如，对于各对A和b，AXB = 100。

如果a == b，则它们是相等的，并且是100的平方根。那是10。

如果其中一个小于10，则必须更大。例如，5 x 20 ==100。一个大于10，另一个大于10。

考虑一下AXB，如果其中一个下降，另一个必须变大才能补偿，因此产品保持100。它们在平方根周围旋转。

101的平方根约为10.049875621。因此，如果您要测试数字101的原始性，则只需要尝试到10个整数，包括10。但是8、9和10本身并不是素数，因此您只需要通过7进行测试，这就是主要。

因为如果有一个数字之一大于10的因素，则一对必须小于10。如果一个较小的不存在，则不可能匹配较大的101。

如果您要测试121，则平方根为11。您必须测试Prime Integers 1至11（包含）才能查看它是否均匀。 11分11次，因此121不是素数。如果您在10点停下来而未测试11，您将错过11。

您必须测试大于2的每个素数，但小于或等于平方根，假设您只在测试奇数。

`

认为 n 不是素数（大于1）。所以有数字 a 和 b 这样

n = ab      (1 < a <= b < n)

通过乘以关系 a<=b 经过 a 和 b 我们得到：

a^2 <= ab
 ab <= b^2

因此：（请注意 n=ab)

a^2 <= n <= b^2

因此：（请注意 a 和 b 积极）

a <= sqrt(n) <= b

因此，如果一个数字（大于1）不是素数，并且我们测试了数字的平方根，我们将找到其中一个因素。

这实际上只是分解和平方根的基本用途。

它似乎是抽象的，但实际上，这只是一个事实，即非prime-number的最大可能阶乘必须是其平方根，因为：

sqrroot(n) * sqrroot(n) = n.

鉴于这一点，如果以上有任何数字 1 在下方或下 sqrroot(n) 均匀分成 n, ， 然后 n 不能是素数。

伪代码示例：

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

让我们假设给定的整数 N 不是Prime，

然后n可以分解为两个因素 a 和 b , 2 <= a, b < N 这样 N = a*b。显然，他们俩都不能比 sqrt(N) 同时。

让我们假设不会失去一般性 a 较小。

现在，如果您找不到任何除数 N 属于该范围 [2, sqrt(N)], ， 这意味着什么？

这意味着 N 没有任何除数 [2, a] 作为 a <= sqrt(N).

所以， a = 1 和 b = n 因此 根据定义， N 是主要的.

...

如果您不满意，请进一步阅读：

许多不同的组合 (a, b) 可能是可能的。假设它们是：

（一个1, ，b1）， （一个2, ，b2）， （一个3, ，b3）， ..... ， （一个k, ，bk）。没有失去普遍性，假设一世 <b一世, 1<= i <=k.

现在，能够证明 N 不是主要的一世 可以进一步分解。我们也知道一世 <= sqrt(N) 因此，您需要检查直到 sqrt(N) 这将覆盖所有一世. 。因此，您将能够得出结论 N 是主要的。

...

因此，要检查一个数字n是否为素数。我们只需要检查n是否可以按数字<= sqroot（n）排除。这是因为，如果我们将n分解为任何两个因素，即x和y，即。 n = xY. X和Y中的每个都不能小于SQRoot（n），因为那时，xy <n x和y的每个都不能大于sqroot（n），因为那时，x*y> n

因此，一个因素必须小于或等于SQRoot（n）（而另一个因素大于或等于SQRoot（n））。因此，要检查n是否为prime，我们只需要检查那些数字<= sqroot（n）。

假设我们有一个数字“ a”，这不是素数[不是素数/复合数字均值 - 一个数字可以均匀地除以1或1本以外的其他数字。例如，6可以均匀地划分为2，也可以分为3，除以1或6]。

6 = 1×6或6 = 2×3

因此，如果“ A”不是素数，那么它可以除以另外两个数字，并说这些数字是“ B”和“ C”。意思是

a = b*c。

现在，如果“ b”或“ c”，它们中的任何一个都大于“ A”的平方根，而不是“ B”和“ C”的乘法，将大于“ A”。

因此，“ b”＆“ c”总是<=“ a”的平方根，以证明方程“ a = b*c”。

由于上述原因，当我们测试一个数字是否为素数时，我们只能检查直到该数字的平方根。

令n为非prime。因此，它至少有两个大于1的整数因素。让F成为此类因素中最小的一个。假设f> sqrt n。那么n/f是一个整数lte sqrt n，因此小于f。因此，F不能是N的最小因素。还原荒谬； n的最小因素必须是lte sqrt n。

给定任何数字 n, ，然后找到其因素的一种方法是获得平方根 p:

sqrt(n) = p

当然，如果我们乘以 p 就本身而言，我们回来了 n:

p*p = n

它可以重新编写为：

a*b = n

在哪里 p = a = b. 。如果 a 然后增加 b 减少维护 a*b = n. 。所以， p 是上限。

为了测试一个数字的原则， n, ，人们会期待一个循环，例如首先关注： 

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

以上循环做的是： 1 <i <n, ，它检查N/I是否是整数（剩余的0）。如果存在一个n/i是整数的i，那么我们可以确定n不是素数，届时循环终止。如果没有i，则n/i是一个整数，则n是素数。

与每种算法一样，我们问： 我们可以做得更好吗？

让我们看看上述循环中发生了什么。

i的顺序：i = 2、3、4，...，n-1

整数检查的顺序进行：j = n/i，n/2，n/3，n/4，...，n/（n-1）

如果对于某些i = a，n/a是整数，则n/a = k（integer）

或n = ak，明显n> k> 1（如果k = 1，则是a = n，但是我永远不会达到n;如果k = n，则a = 1，但我开始形式2）

另外，n/k = a，如上所述，a是i sO s sO s so n> a> 1的值。

因此，A和K是1和N之间的整数（独家）。由于，我在该范围内，在某些迭代i = a以及其他一些迭代i = k的情况下达到了每个整数。如果n的原始测试失败了（a，k），则最大值（a，k）也将失败。因此，除非最小（a，k）= max（a，k）（其中两次检查减少到一个）IE，a = k，否则我们只需要检查这两种情况之一暗示a = sqrt（n）。

换句话说，如果n的原始测试失败了某些i> = sqrt（n）（ie，max（a，k）），那么对于某些i <= n（即，k））。因此，如果我们对i = 2进行SQRT（n）的测试就足够了。

任何复合号码都是素数的产物。

说 n = p1 * p2, ， 在哪里 p2 > p1 它们是素数。

如果 n % p1 === 0 然后 n 是一个复合号码。

如果 n % p2 === 0 然后猜怎么着 n % p1 === 0 也！

因此，没有办法 n % p2 === 0 但 n % p1 !== 0 同时。换句话说，如果复合号码 n 可以均匀地分割p2，p3 ... pi （更大的因素）必须将其除以最低因素 P1 也。事实证明最低因素 p1 <= Math.square(n) 总是正确的。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top