为什么我们要检查质数的平方根以确定它是否为质数？ [英] Why do we check up to the square root of a prime number to determine if it is prime?

问题描述

要测试一个数字是否为质数，为什么我们必须测试该数字是否只能整除该数字的平方根？

To test whether a number is prime or not, why do we have to test whether it is divisible only up to the square root of that number?

推荐答案

如果数字 n 不是质数，则可以将其分为两个因素 a 和 b ：

If a number n is not a prime, it can be factored into two factors a and b:

n = a * b

现在 a 和 b 不能都大于 n 的平方根，因为从那以后乘积 a * b 将大于 sqrt（n）* sqrt（n）= n 。因此，在 n 的任何因式分解中，至少一个因子必须小于 n 的平方根，并且如果找不到小于或等于平方根的因子，则 n 必须是质数。

Now a and b can't be both greater than the square root of n, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. So in any factorization of n, at least one of the factors must be smaller than the square root of n, and if we can't find any factors less than or equal to the square root, n must be a prime.

这篇关于为什么我们要检查质数的平方根以确定它是否为质数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！