专栏首页数据结构与算法高效判断素数方法

高效判断素数方法

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P2375 动物园

    题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决...

    attack
  • BZOJ 3932: [CQOI2015]任务查询系统(主席树)

    attack
  • P1577 切绳子

    题目描述 有N条绳子,它们的长度分别为Li。如果从它们中切割出K条长度相同的 绳子,这K条绳子每条最长能有多长?答案保留到小数点后2位。 输入输出格式 输入格式...

    attack
  • 欧拉计划 Problem7

    题目: 第10001个素数 列出前6个素数,它们分别是2、3、5、7、11和13。我们可以看出,第6个素数是13。

    用户4492257
  • iOS简易蓝牙对战五子棋游戏设计思路之二——核心棋盘逻辑与胜负判定算法

        上一篇博客我们介绍了在开发一款蓝牙对战五子棋游戏中核心的蓝牙通讯框架的设计与编写,本篇博客将来完成独立的棋盘逻辑与胜负判定算法。上篇博客地址如下:

    珲少
  • 【leetcode刷题】T193-各位相加

    https://leetcode-cn.com/problems/add-digits/

    木又AI帮
  • 排序算法总结

    关于各种排序算法的总结表格,这里偷个懒直接用Simple life的博客http://blog.csdn.net/whuslei/article/details...

    用户1215536
  • 数组变换

    牛牛有一个数组,里面的数可能不相等,现在他想把数组变为:所有的数都相等。问是否可行。 牛牛可以进行的操作是:将数组中的任意一个数改为这个数的两倍。 这个...

    AI那点小事
  • 插入排序与希尔排序

    插入排序描述:有一个数组num[n];它有n个元素,假设其中n-1已经排好序了,那么把剩余的那个元素插入到合适的位置即可,这样就完成了排序。根据这个思想,很明显...

    zy010101
  • Leetcode 476. Number Complement

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan

扫码关注云+社区

领取腾讯云代金券