c语言为什么判断素数用sqrt ？拜托各位大神

Question

scanf("%d",&n); k=sqrt(n) for(i=2;i<=k;i++) if(k%i==0)bresk; 如上：为什么不直接判断n%i，而是2-sqrt（n）这个范围？（主要是为什么可以平方根）

Answer 1

你好，我们假设一个数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； 明白了吧？

Answer 2

k=sqrt(n)
for(i=2;i<=k;i++)
中的k有利于减少无用的循环次数。
因为根据数学推理可知，判断一个数是不是素数不用都除于所有小于此数的数的。只要除数小于该数的平方根就足以判断该数是不是素数了。
这也体现C语言的程序简洁特点。