我们在日常判断素数的程序中常用到如下代码
//判断数num是不是素数
for(i=2;i<num;i++){
if(num%i==0)
return 0;
return 1;
}
这样写无疑是没有问题的，但是我们实际做题可能会有算法时间复杂度的要求，或者说数据大的时候我们会等很久，算法效率低，那么有没有一种好的算法可以更快地判断是不是素数呢？
当然了，先附上代码段
//判断数num是不是素数
for(i=2;i<=sqrt(num);i++){
if(num%i==0)
return 0;
return 1;
}
sqrt()函数是用来判断开根号的，那么我们这样用是为何呢？
比如想判断20是不是素数，我们都知道素数是除了1和数本身没有其他公约数的数，我们看，20可以分成如下公因子：
如果我们用老办法i=2到20一个一个判断是可以，但是没有必要
因为，我们可以使用sqrt来判断
//判断数20是不是素数
for(i=2;i<=sqrt(20);i++){
if(num%i==0)
return 0;
return 1;
}
|
|
楼主
