为什么我们要检查一个数的平方根来确定该数是否是素数？

Question

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

Answer 1

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

n = a * b

现在a和 b 不能同时大于 n 的平方根，因为这样乘积 a * b 将大于 sqrt(n) * sqrt(n) = n。因此，在n的任何分解中，至少有一个因子必须小于或等于n的平方根，并且如果我们找不到任何小于或等于n的因子大于或等于平方根，n 必须是质数。

Answer 2

假设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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

sqrroot(n) * sqrroot(n) = n。

鉴于此，如果任何大于 1 且小于或等于 sqrroot(n) 的整数均分为 < em>n，则 n 不能是素数。

伪代码示例：

i = 2;

is_prime = true;

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

Answer 6

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

那么 N 可以分解为两个因子 a 和 b ， 2 2 2 2 。 =a，b＜ N 使得 N = a*b。
显然，它们不能同时大于 sqrt(N)。

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

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

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

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

...

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

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

(a₁, b₁), (a₂, b₂), ( a₃, b₃), ..... , (a_k, b_k).不失一般性，假设 a_i < b_i，1<= i<=k。

现在，为了能够证明 N 不是素数，只要证明 _i 中没有一个可以被进一步分解就足够了。我们还知道 a_i <= sqrt(N) 因此您需要检查直到 sqrt(N) 这将涵盖所有一个_i。因此，您将能够得出 N 是否是质数的结论。

...

Answer 7

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

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

Answer 8

假设我们有一个数字“a”，它不是质数[非质数/合数意味着 - 一个可以被 1 或它本身以外的数字整除的数字。例如，6 可以被 2、或 3、以及 1 或 6 整除]。

6 = 1 × 6 或 6 = 2 × 3

所以现在如果“a”不是质数，那么它可以被另外两个数字整除，假设这些数字是“b”和“c”。这意味着

a=b*c。

现在，如果“b”或“c”，则它们中的任何一个都大于“a”的平方根，而不是“b”与“c”的乘积。 “c”将大于“a”。

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

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

Answer 9

给定任何数字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 可以是实数（即带分数）。现在我们只需遍历 p 的整个范围，而不是遍历 n 的整个范围。另一个 p 是镜像副本，因此实际上我们将范围减半。然后，现在我发现我们实际上可以继续重新计算平方根，并对 p 进一步进行一半的范围。

Answer 10

令 n 为非素数。因此，它至少有两个大于 1 的整数因子。令 f 为 n 个这样的因子中最小的一个。假设f>开方那么 n/f 是一个 ≤ sqrt n 的整数，因此小于 f。因此，f 不可能是n 的最小因子。反证法； n 的最小因子必​​须 ≤ sqrt n。

Answer 11

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

假设n = p1 * p2，其中p2 > p1 并且它们是素数。

如果 n % p1 === 0 则 n 是一个合数。

如果n % p2 === 0，那么也猜一下n % p1 === 0！

所以不可能同时 if n % p2 === 0 但 n % p1 !== 0 。
换句话说，如果合数n可以被整除
p2,p3...pi（它的较大因子）也必须除以它的最小因子p1。
事实证明，最低因子 p1 <= Math.square(n) 始终为真。

Answer 12

是的，正如上面正确解释的那样，迭代到数字平方根的 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>

Answer 13

要测试数字 n 的素性，首先需要一个如下所示的循环：

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

上面的循环的作用是：对于给定的 1 1 1 1 1 1 1 我< n，它检查 n/i 是否为整数（余数为 0）。如果存在一个i，其中n/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（整数）

或 n = ak，显然 n > 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 = a，以及在其他迭代中 i = k，i 达到该范围内的每个整数。如果 n 的素性测试对于 min(a,k) 失败，那么对于 max(a,k) 也将失败。所以我们只需要检查这两种情况之一，除非 min(a,k) = max(a,k) （其中两个检查减少到一个）即 a = k ，此时 a*a = n，其中意味着 a = sqrt(n)。

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