高效判断素数方法
孪生素数： 所谓孪生素数指的是间隔为 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的倍数。
由上面的规律可以推出下面结论：
若x≧1且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的倍数。
素数出现规律：
当n≧5时，如果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 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define LL long long
6 using namespace std;
7 int n,m,p;
8 bool judge(int num)
9 {
10 if(num==2||num==3)
11 return true;
12
13 if(num%6!=1&&num%6!=5)
14 return false;
15
16 for(int i=5;i*i<=num;i+=6)
17 if(num%i==0||num%(i+2)==0)
18 return false;
19
20 return true;
21 }
22 int main()
23 {
24 scanf("%d%d",&n,&m);
25 for(int i=1;i<=m;i++)
26 {
27 scanf("%d",&p);
28 if(judge(p)&&p!=1)printf("Yes\n");
29 else printf("No\n");
30 }
31 return 0;
32 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-05-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
