在C语言中求素数时,为何只需要出从2 到 根号N

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/15 13:50:57

在C语言中求素数时,为何只需要出从2 到 根号N
在C语言中求素数时,为何只需要出从2 到 根号N

在C语言中求素数时,为何只需要出从2 到 根号N
这么想吧:一个数N,它是根号N的平方,那么如果它有其他约数的话,假设为A,B(约数肯定要成对出现的)必然有一个大于根号N,另一个小于根号N(显然如果都大于根号N,那相乘结果会大于N;反之会小于N),所以在找的时候,只需找到根号N即可,大于根号N的那些肯定跟小于N的成对匹配,如果小于根号N的约数都没有,显然也没有大于根号N的数与它匹配了