博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
高效判断素数方法
阅读量:5062 次
发布时间:2019-06-12

本文共 1320 字,大约阅读时间需要 4 分钟。

孪生素数: 所谓孪生素数指的是间隔为 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
2 #include
3 #include
4 #include
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 }

 

转载于:https://www.cnblogs.com/zwfymqz/p/6873669.html

你可能感兴趣的文章
codeforces global round 1题解搬运
查看>>
python os模块
查看>>
Codeforces 719B Anatoly and Cockroaches
查看>>
jenkins常用插件汇总
查看>>
c# 泛型+反射
查看>>
第九章 前后查找
查看>>
Python学习资料
查看>>
多服务器操作利器 - Polysh
查看>>
[LeetCode] Candy
查看>>
Jmeter学习系列----3 配置元件之计数器
查看>>
jQuery 自定义函数
查看>>
jq 杂
查看>>
jquery datagrid 后台获取datatable处理成正确的json字符串
查看>>
作业一
查看>>
AJAX
查看>>
ActiveMQ与spring整合
查看>>
web服务器
查看>>
Git的使用--打tag
查看>>
F# 编程 借助 F# 构建 MVVM 应用程序
查看>>
ACFUN切换代码自用。。。
查看>>