为什么我们检查高达质数的平方根，以确定它是否是黄金？ [英] Why do we check upto 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 upto 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 将大于 N 。因此，这些因素至少有一个必须小于或等于平方根 N ，并检查 N 是素数，我们只需要测试因子小于或等于平方根

If both a and b were greater than the square root of n, a*b would be greater than n. So at least one of those factors must be less or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.

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