高效判断素数方法
2012/8/2 18:07

---

孪生素数： 所谓孪生素数指的是间隔为 2 的相邻素数，它们之间的距离已经近得不能再近了。

若n≥6且n-1和n+1为孪生素数，那么n一定是6的倍数。证明：∵ n-1和n+1是素数 ┈┈┈┈┈ ①∴ n-1和n+1是奇数∴ n是偶数，即n是2的倍数 ┈┈┈┈┈ ②假设n不是3的倍数，得：n=3x+1 或 n=3x+2，如果n=3x+1，则n-1=3x，与①违背，故n≠3x+1；如果n=3x+2，则n+1=3(x+1)，与①违背，故n≠3x+2；∴假设不成立，即n是3的倍数，又有②得结论：n是6的倍数。
由上面的规律可以推出下面结论：若x1且n=6x-1或n=6x+1不是素数，那么n一定不是2和3的倍数。证明：∵n=6x-1或n=6x+1，即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。∴n一定不是2和3的倍数。
素数出现规律：当n5时，如果n为素数，那么n mod 6 = 1 或 n mod 6 == 5，即n一定出现在6x（x≥1）两侧。证明：当x≥1时，有如下表示方法：┈┈ 6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1┈┈不在6x两侧的数为6x+2，6x+3，6x+4，即2(3x+1)，3(2x+1)，2(3x+2)，它们一定不是素数，所以素数一定出现在6x的两侧。
高效判断一个大于1的数是否为素数：

---

bool isPrime(int num){if (num == 2 || num == 3){return true;}if (num % 6 != 1 && num % 6 != 5){return false;}for (int i = 5; i*i <= num; i += 6){if (num % i == 0 || num % (i+2) == 0){return false;}}return true;}

5楼leihengxin昨天 21:11

不错。

4楼xxyj6450昨天 18:06

如果n=3x+1，则n-1=3x，与①违背，故n≠3x+1；n如果n=3x+2，则n+1=3(x+1)，与①违背，故n≠3x+2；nn这两句成立吗?nn-1=3x,当x为奇数时是不违背①的nn+1=3(x+1),当x为偶数时也不违背①啊

Re: jefferson327昨天 18:08

只有当x = 1时才不成立，但是你≥6，故x ≠1，所以楼主这样证明应当没错。回复xxyj6450

Re: jefferson327昨天 21:11

回复jefferson327nn≥6.。。。。。。。

3楼leihengxin昨天 14:35

嗯。

2楼Yangxx319昨天 12:22

楼主的数学功底好强。。

1楼bao110908昨天 12:03

这个还是平方根算法，对于大数建议采用 Miller-Rabin 素性测试