判断一个数是否是素数的讨论

最常见的方法是i*i<=x,i++,这种方法算是比较常见，并且较为实用，这里讨论的是另一种方法。

判断一个数是否是素数，只需要让x与素数进行判断求余就可以。

6*i一定不是素数

6*i+1可能是素数

6*i+2一定不是素数

6*i+3一定不是素数

6*i+4一定不是素数

6*i+5可能是素数

所以，见代码：

bool isprime(int a){
    if(a==2||a==3||a==5) return true;
    if(a%2==0||a%3==0||a==1) return false;
    for(int i=5;i<=sqrt(a);i+=6){
        if(a%i==0||a%(i+2)==0) return false;
    }
    return true;
}

而且，如果使用i*i<=a，复杂度会比较高，这是因为每次都会计算一个乘法。

但是使用i<sqrt(a)，复杂度会比较低，我认为在c++的编译器会自动进行循环优化，就是并不是每次循环都重新计算一次sqrt(a)，而是从始至终只计算一次。

判断一个数是否是素数的讨论

原文：https://www.cnblogs.com/sunjianzhao/p/14013305.html