首页 > 代码库 > 为什么质数检验到 N的开方 就可以结束了

为什么质数检验到 N的开方 就可以结束了

以为所有N的除数都是以根号N为轴对称的。

例如16的开方为4;

16%1 == 0

则1 与 16 都是16的除数。

16%2 == 0

则2 与 8 都是16的除数。

16%4 ==0

则4 为16 的除数。

如果继续查找,找到 8

则已经添加。

所以判断一个数为质数与否的复杂度为O(根号N)

为什么质数检验到 N的开方 就可以结束了