高效判断素数算法(6倍原理)

原理：

除了2和3外，其余素数都与6的倍数相邻，这些素数都满足6n±1，也就是说这些素数都分布在6的倍数的邻数上。总结为一句话：大于等于5的质数一定和6的倍数相邻。例如：5、7， 11、13、17等。但是与6的倍数相邻的不一定是素数，有可能是6倍邻数的倍数，例如25、35、49，这些数就分别是5，7的倍数。

这是个trivial的素数分布特征，因模6的余数中只有1和5与6互素，故从5开始的素数必与6的倍数相邻。

设计：

算法设计的时候，除了2和3外需要判断一个数是否为素数。

第一步：先判断是否为6倍邻数，如果是则执行第二步；

第二步：判断这个数是否为6倍邻数的倍数，如若不是则这个数为素数

分析：

1、大于等于5的素数必定为6倍邻数证明

6倍以外的数分别有：6n+1，6n+2，6n+3，6n+4，6n+5

其中6n+2，6n+3，6n+4三个数都可以分解：

6n+2=2(3n+1)

6n+3=3(2n+1)

6n+4=2(3n+2)

所以以上三个数必不可能是素数，剩下的只有6n+1，6n+5可能存在素数

2、6n+1和6n+5的素数判断

在判断6n+1和6n+5是否为素数过程中只需判断这个数是否为6倍邻数的倍数即可断定

为何不需要判断这个数是否为6n+2，6n+3，6n+4的倍数

首先，6n+2，6n+4为偶数，不可能是6n+1，6n+5这个两个奇数的因数，自然就不用判断

然后，6n+3=3(2n+1)，所以6n+3必为3的倍数，3的倍数不分布在6n+1上，也不分布在6n+5上。

因为

6n+13=2n+13

\frac{6n+1}{3}=2n+{{1} \over {3}}

36n+1​=2n+31​

6n+53=2n+1+23

\frac{6n+5}{3}=2n+1+{{2} \over {3}}

36n+5​=2n+1+32​

当n为整数时，无论n取何值，上面这两个式子都不可能为整数。

所以6n+1和6n+5，不可能为6n+3的倍数。

故6n+1和6n+5，只可能为6m+1和6m+5的倍数。

存在6倍邻数的两个因数是6倍邻数。

素数判断函数

bool isprime(int num) {

if (num == 2 || num == 3) {

return true;

}

//如果不与6的倍数相邻，肯定不是素数

if (num % 6 != 1 && num % 6 != 5) {

return false;

}

//对6倍邻数进行判断,是否为6倍邻数的倍数

for (int i = 5; i <= sqrt(num); i += 6) {

if (num % i == 0 || num % (i + 2) == 0) {

return false;

}

}

return true;

}