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

Question

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

Answer 1

如果数字n不是素,它可以分解成两个因素a和b:

n = a * b

如果两个a和b比的平方根更大n,那么a * b将大于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

更直观的解释是: -

100的平方根是10.假设axb = 100,对于各种a和b对.

如果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.您必须测试1到11(包括)的素数整数,以查看它是否均匀进入.11进11次,所以121不是素数.如果你已经停在10点,而没有经过测试11,你就错过了11点.

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

`

Answer 5

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

我们假设给定的整数N不是素数,

然后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)都是可能的.让我们说它们是:

(a ₁,b ₁),(a ₂,b ₂),(a ₃,b ₃),.....,(a _k,b _k).不失一般性,假设一个_i <b _i , 1<= i <=k.

现在,为了能够证明这N不是素数,足以证明_i中没有一个可以进一步分解.而且我们也知道一个_i <= sqrt(N)因此你需要检查sqrt(N)哪个将覆盖所有_i.因此,你将能够得出结论是否N是素数.

...

Answer 7

这些只是分解和平方根的基本用法.

它可能看起来是抽象的,但实际上它只是因为非素数的最大可能因子必须是它的平方根,因为:

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;
}

Answer 8

因此要检查数字N是否为质数。我们只需要检查N是否可被数字<= SQROOT（N）整除。这是因为，如果我们将N分解为任意两个因子，则说X和Y。N = XY。X和Y的每个不能小于SQROOT（N），因为X Y <N X和Y的每个都不可以大于SQROOT（N），因为X * Y> N

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

Answer 9

假设我们有一个数字“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”。

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