判断素数的快速算法sqrt（）
我们在⽇常判断素数的程序中常⽤到如下代码
//判断数num是不是素数
for(i=2;i<num;i++){
if(num%i==0)
return 0;
return 1;
}
这样写⽆疑是没有问题的，但是我们实际做题可能会有算法时间复杂度的要求，或者说数据⼤的时候我们会等很久，算法效率低，那么有没有⼀种好的算法可以更快地判断是不是素数呢？
c++判断素数当然了，先附上代码段
//判断数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;
}
我们看到sqrt(20)的值是
其实我们只需要判断前半段就⾏，因为有2肯定有10，有4肯定有5

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。