为什么我们要检查素数的平方根来确定它是否是素数? [英] 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屋！