C语言中判断素数涉及sqrt的问题

Python019

C语言中判断素数涉及sqrt的问题,第1张

假设一个数a那么a=(a^1/2)*(a^1/2)如果a不是素数；那么a有一个因子ba=b*c那么a的因子中（b或c）必定有一个是小于等于a^1/2的；所以判断的时候不用判断到1-a，只需要1-a^1/2；一个数的因子不可能大于其平方根，因此可以缩小范围。

如果不用素数筛法的话，一般都是for求的。

设该数为n，则若该数为质数，则有a*b=n始终成立(a,b>1)。

当a<=sqrt(n)时

n/sqrt(n)=sqrt(n)

则n/a>=sqrt(n)

n/a=b

所以b>=sqrt(n)

可以发现，一个质数的两个因数，至少有其中一个小于等于根号n。

可推得若一个整数没有至少一个因数小于根号n，则它为素数。

综上，sqrt(n)为判断素数的最小临界条件。