素数判断问题:为什么从2开始到该整数的平方根网上有很多判断素数的编程题,算法中为什么要从2开始到该整数的平方根,从2开始到该整数-1这个范围很容易理解.
问题描述：
素数判断问题:为什么从2开始到该整数的平方根
网上有很多判断素数的编程题,算法中为什么要从2开始到该整数的平方根,从2开始到该整数-1这个范围很容易理解.
答
判断一个数是否素数,只需判断它是否有非1,非本身的正因子.
一般算法都是从2开始判断,设该数是N,假如N有大于 根号N 的因子,那么它的另一个因子必小于 根号N,那么计算机运算时查到这个因子时就可判断它不是素数,因此只需到平方根,而不必查到 N-1