作业帮 > 综合 > 作业

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

来源:学生作业帮 编辑:大师作文网作业帮 分类:综合作业 时间:2024/11/17 11:31:06
在C语言中求素数时,为何只需要出从2 到 根号N
在C语言中求素数时,为何只需要出从2 到 根号N
这么想吧:一个数N,它是根号N的平方,那么如果它有其他约数的话,假设为A,B(约数肯定要成对出现的)必然有一个大于根号N,另一个小于根号N(显然如果都大于根号N,那相乘结果会大于N;反之会小于N),所以在找的时候,只需找到根号N即可,大于根号N的那些肯定跟小于N的成对匹配,如果小于根号N的约数都没有,显然也没有大于根号N的数与它匹配了