Question

c语言用sqrt求素数原理

c语言用sqrt求素数原理

Answer 1

如果不用素数筛法的话，一般都是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)为判断素数的最小临界条件。