506

为了检验一个数是否是素数，为什么我们必须检验它是否只能被该数的平方根整除？

4

13 回答 13

832

如果一个数n不是素数，它可以分解为两个因式a和b：

n = a * b

现在a和b不能都大于 的平方根n，因为那时乘积a * b将大于sqrt(n) * sqrt(n) = n。所以在 的任何因式分解中n，至少有一个因数必须小于 的平方根n，如果我们找不到任何小于或等于平方根的因数，则n必须是素数。

于 2011-04-27T22:04:05.237 回答
374

m = sqrt(n)那就说吧m × m = n。现在 ifn不是素数 thenn可以写成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

在所有 3 种情况下，min(a, b) ≤ m。因此，如果我们搜索直到m，我们一定会找到 的至少一个因子n，这足以证明它n不是素数。

于 2011-04-28T05:14:16.470 回答
66

因为如果一个因子大于 n 的平方根，那么与它相乘等于 n 的另一个因子必然小于 n 的平方根。

于 2011-04-27T22:04:09.717 回答
26

假设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）不是素数，并且我们测试可除性到该数的平方根，我们将找到其中一个因数。

于 2015-07-30T23:39:00.497 回答
9

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

它可能看起来很抽象，但实际上它只是基于这样一个事实，即非质数的最大可能阶乘必须是它的平方根，因为：

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;
}
于 2015-11-28T01:28:06.660 回答
8

假设给定的整数N不是素数，

然后 N 可以分解为两个因素a和b， 2 <= a, b < N这样N = a*b。显然，它们两者不能同时大于sqrt(N)。

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

N现在，如果您在 range 中找不到任何除数[2, sqrt(N)]，那是什么意思？

这意味着asN中没有任何除数。[2, a]a <= sqrt(N)

因此，a = 1因此b = n根据定义，N是素数。

...

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

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

(a 1 , b 1 ), (a 2 , b 2 ), (a 3 , b 3 ), ... , (a k , b k )。不失一般性，假设 a i < b i , 1<= i <=k。

现在，为了能够证明它N不是素数，证明没有一个i可以被进一步分解就足够了。而且我们也知道 a i <= sqrt(N)，因此您需要检查直到sqrt(N)覆盖所有 a i。因此，您将能够得出是否N为素数的结论。

...

于 2017-07-09T19:41:09.547 回答
7

假设我们有一个数字“a”，它不是素数[不是素数/复合数意味着 - 一个可以被除 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”。

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

于 2017-07-20T13:28:05.953 回答
6

所以要检查一个数字 N 是否是素数。我们只需要检查 N 是否可以被数字整除<=SQROOT(N)。这是因为，如果我们将 N 分解为任意两个因子，例如 X 和 Y，即。N=X Y。X 和 Y 中的每一个都不能小于 SQROOT(N)，因为这样，X Y < N X 和 Y 中的每一个都不能大于 SQROOT(N)，因为这样，X*Y > N

因此，一个因子必须小于或等于 SQROOT(N) （而另一个因子大于或等于 SQROOT(N) ）。因此，要检查 N 是否为素数，我们只需要检查这些数字 <= SQROOT(N)。

于 2017-05-10T13:43:00.453 回答
3

给定任何数字n，找到其因数的一种方法是求其平方根p：

sqrt(n) = p

当然，如果我们p自己相乘，那么我们会返回n：

p*p = n

它可以重写为：

a*b = n

哪里p = a = b。如果a增加，则b减少维持a*b = n。因此，p是上限。

更新：我今天再次重新阅读这个答案，它对我来说变得更清楚了。该值p不一定表示整数，因为如果是整数，则n不会是素数。因此，p可能是一个实数（即，带有分数）。而不是遍历整个范围n，现在我们只需要遍历整个范围p。另一个p是镜像副本，因此实际上我们将范围减半。然后，现在我看到我们实际上可以继续重新做，square root并将其扩大p到一半的范围。

于 2018-09-03T02:38:18.220 回答
3

设 n 为非素数。因此，它至少有两个大于 1 的整数因子。设 f 是 n 的这些因子中的最小值。假设 f > sqrt n。那么 n/f 是一个整数 ≤ sqrt n，因此小于 f。因此，f 不可能是 n 的最小因子。减少荒谬；n 的最小因子必​​须≤ sqrt n。

于 2016-01-24T00:01:35.010 回答
2

是的，正如上面正确解释的那样，迭代到 Math.floor 一个数字的平方根来检查它的素数就足够了（因为sqrt涵盖了所有可能的除法情况；并且Math.floor，因为上面的任何整数sqrt都已经超出了它的范围）。

这是一个可运行的 JavaScript 代码片段，它代表了这种方法的一个简单实现——它的“运行时友好性”足以处理相当大的数字（我尝试检查质数和非质数，直到 10**12，即 1万亿，将结果与在线素数数据库进行比较，即使在我的廉价手机上也没有遇到错误或滞后）：

function isPrime(num) {
  if (num % 2 === 0 || num < 3 || !Number.isSafeInteger(num)) {
    return num === 2;
  } else {
    const sqrt = Math.floor(Math.sqrt(num));
    for (let i = 3; i <= sqrt; i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  }
}
<label for="inp">Enter a number and click "Check!":</label><br>
<input type="number" id="inp"></input>
<button onclick="alert(isPrime(+document.getElementById('inp').value) ? 'Prime' : 'Not prime')" type="button">Check!</button>

于 2021-02-16T13:57:30.857 回答
2

任何合数都是素数的乘积。

比方说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)总是正确的。

于 2018-12-18T09:52:58.210 回答
1

要测试一个数字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，但 i 从未达到 n；如果 k = n，则 a = 1，但 i 从 2 开始）

此外，n/k = a，如上所述，a 是 i 的值，因此 n > a > 1。

因此，a 和 k 都是 1 和 n 之间的整数（不包括）。因为，i 达到了该范围内的每个整数，在某个迭代 i = a，而在另一个迭代 i = k。如果 n 的素数测试对 min(a,k) 失败，它也会对 max(a,k) 失败。所以我们只需要检查这两种情况之一，除非 min(a,k) = max(a,k) （其中两个检查减少到一个）即 a = k ，此时 a*a = n，意味着 a = sqrt(n)。

换句话说，如果对于某些 i >= sqrt(n)（即 max(a,k)），n 的素性检验失败，那么对于某些 i <= n（即 min(a ,k))。因此，如果我们运行 i = 2 到 sqrt(n) 的测试就足够了。

于 2017-06-29T17:43:44.837 回答