加载中…为什么求素数只要除到平方根就行了？
(2013-07-31 17:13:36)
标签：
it |
分类： C/C |
可以减少循环次数，素数是因子为1和本身， 如果数c不是素数，则还有其他因子，其中的因子，假如为a,b. 其中必有一个大于sqrt(c) ，一个小于sqrt(c) 。 所以m必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。
void main（）
{
int
n,i,k
for(n=2;n<=100;n+=2)
{
k=sqrt(n);
for(i=2;i
{
if(n%i==0) break;
if(i>=k)
printf("\t-",n)
}
}
}
喜欢
0
赠金笔