高效判断素数方法

2018-06-17 22:34:12来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

孪生素数: 所谓孪生素数指的是间隔为 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+26x+36x+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 }

 


标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1203 [USACO1.1]坏掉的项链Broken Necklace

下一篇:Leetcode:9. Palindrome Number