快速判断质数

  • Post author:
  • Post category:其他


下图是一百以内质素表

观察上图,有两个规律

规律一:当数大于10之后,质素的结尾均以1,3,7,9结尾。

因为大于10以后,以0,2,4,6,8结尾的数均能被2整除,以5结尾的数均能够被5整除,就只剩下以1,3,7,9结尾的质数了。

规律二:从5开始,质数均分布在6的倍数附近(左右),比如12,18,24,30等附近均有质数。

推理过程

由于6以上的数都可以用 6x + n (x为正整数,n为非负整数,且n<6),接下来将以 6+0 ,6+1等表示所有数字。

因为6x+0(x为正整数)一定能够被6整除,6x+1不确定,而6x+2一定能被2整除,6x+3一定能够被3整除,6x+4一定能被2整除,6x+5不确定,就只有6x+1和6x+5不确定是不是质数,而6x+5又等于6x-1,也就是6x+1和6x-1不确定是不是质数,即6的倍数两边可能会出现质数。

下面中给出判断质数的代码:

bool is_prime(int x){
    if(x==1)
        return false;
    if(x==2||x==3)
        return true;
    if(x%6!=1&&x%6!=5)//规律二
        return false;
    int s=sqrt(x);
    for(int i=5;i<=s;i+=6)//规律二
        if(x%i==0||x%(i+2)==0)
            return false;
    return true;
}

关于判断质因数我有一个自己的猜想(没有被证实):

而且结合规律一和规律二,我有一个大胆的想法,就是比如说6的倍数是以6结尾的,比如36,那么它的右边必出现一个质数,即37,就是比如说6的倍数是以4结尾的,比如24,那么它的左边必出现一个质数,即23。



版权声明:本文为qq_38781075原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。