快速判断一个数是否为素数

佚名 6年前 (2019-04-15) 随笔 1531人围观抢沙发百度已收录

对于每一个大于等于5的数，它只有在6的两侧才可能是素数

因为大于等于5的数可以表示为6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5....

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

而6x,6x+2=2(3x+1),6x+3=3(x+1),6x+4=2(3x+2)都不可能是素数，

所以我们对于一个数n，直接先判断它模6是否余5或余1，不是的话直接返回false

但是是的话也不一定是素数，还要再判断一下，具体判断的方法是：

我们知道每个数都能进行质因数分解，所以我们只要判断用它除前面的素数能否除的尽即可，而6x+1,6x+5这样的数显然不可能除的尽2和3，所以我们从5开始判断，

下一个除以7，按照上面的讨论，下一个为11和13，以此类推，可以把步长增加到6来加快运行速度

代码如下：

bool is_prime(long long x){
    if(x==1)
        return false;
    if(x==2||x==3)
        return true;
    if(x%6!=1&&x%6!=5)
        return false;
    int s=sqrt(x);
    for(int i=5;i<=s;i+=6)
        if(x%i==0||x%(i+2)==0)
            return false;
    return true;
}