我们在日常判断素数的程序中经常使用以下代码
判断//数num是否为素数for (I=2； inum； I ) if(num%I==0)返回0； 返回1； }这样写没问题，但实际上解决问题可能需要算法的时间复杂性要求。 或者，数据大的时候要等很久，算法效率很低，有没有更快判断是否是素数的好算法呢？
当然，首先附上代码段
判断//数num是否为素数for (I=2； I=sqrt(num； I ) if(num%I==0)返回0； 返回1； } sqrt ) )函数用于判断开根号，我们为什么要这样使用呢？
例如，如果尝试确定20是否为素数，则发现素数是除1和数本身以外没有公约数的数。 20可分为以下公式因子：
我们用旧方法从i=2到20逐一判断就可以了，但没有必要
为什么这么说，是因为我们可以使用sqrt进行判断
//判断数20是否为素数for (I=2； I=sqrt(20； I ) if(num%I==0)返回0； 返回1； }
发现sqrt(20 )的值为4.47 .
其实只判断前半部分就可以了。 因为有2就一定有10，有4就一定有5