之前有刷到孪生素数的题,整理一下代码备用。
理论基础
任何一个自然数,总可以表示成如下形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5(N=0,1,2,…..)
做一下变形得:
6N,6N+1,2(3N+1),3(2N+1),2(3N+2),6N+5(N=0,1,2,…..)
很明显6N、2(3N+1)、3(2N+1)、2(3N+2)都能被2或者3整除,故不可能是素数
只有6N+1和6N+5可能是素数。所以在做素数的检查时,我们可以将步长由原来的i+=2改成i+=6
示例代码

bool is_prime(int n)
{
    if(n==2 || n==3) return false;
    if(n%6!=1 && n%6!=5) return false;

    //到这里,留下来的n只可能是6N+1或者6N+5;
    int div = 5;
    int t = n/div;
    while(t>=div)
    {
        //n可能是(6N+1)与(6N+5)两个因子的乘积,故需要在这里进行判断;
        if(n%div==0 || n%(div+2)==0) return false;
        div += 6;
        t = n/div;
    }
    return true;
}