本文目录一览:
C语言中判断素数涉及sqrt的问题
假设一个数a;
那么a=(a^1/2)*(a^1/2);
如果a不是素数;
那么a有一个因子b
a=b*c;
那么a的因子中(b或c)必定有一个是小于等于a^1/2的;
所以判断的时候不用判断到1-a,只需要1-a^1/2;
一个数的因子不可能大于其平方根,因此可以缩小范围。
c语言用sqrt求素数原理
如果不用素数筛法的话,一般都是for求的。
设该数为n,则若该数为质数,则有a*b=n始终成立(a,b1)。
当a=sqrt(n)时
n/sqrt(n)=sqrt(n)
则n/a=sqrt(n)
n/a=b
所以b=sqrt(n)
可以发现,一个质数的两个因数,至少有其中一个小于等于根号n。
可推得若一个整数没有至少一个因数小于根号n,则它为素数。
综上,sqrt(n)为判断素数的最小临界条件。
c语言中,用sqrt()素数的判定
当那个for循环结束了,,那个i就是k+1了!!而当那个i=k+1时,说明for一直运行完都没有break,所以m就是素数!!!