简单的C语言问题

Question

我是初学者，当判断一个数是不是素数的时候，
为什么要 k=sqrt(n) 回答时请不要套用公式之类的，
尽量用大白话。谢谢了。。。

Answer 1

也可以不用啊，用的话就是少计算很多次，提高程序效率。
判断一个数n是否是素数，通常你可以从2开始循环到n，看是否有n的因数，但是实际上不需要循环到n，只需要从2循环判断到sqrn(n)就可以了，如果这个范围内没有n的因数，那么n就是素数，这样就不必判断sqrn(n)到n之间的数字了，可以显著降低程序的时间复杂度，提高程序运行效率。
比如求10001是不是素数，如果从2到10001需要运行9999次循环，而如果运行到sqrn(10001)即100则只需要运行99次循环判断就可以了。

Answer 2

一般是因为 判断n是否为素数，只要判断n能否被2，3，4，5，6，……整除即可。而除数最大只需要到 n的 平方根即可。

比如 n=51 ;则只需要判断51 能否被
2,3,4,5,6,7 即可。后面的除数不用判断了。本回答被提问者采纳

Answer 3

sqrt(n)以后再循环从2到k不就可以少判断一半的数吗!可以让程序快啊!你想2*8=16 4*4=16 8*2=16 其实判断到 4就可以了,8就没必要判断了所以n开方在判断.明白吗?我表达能力比较差,呵呵