美文网首页
判断一个数是否是素数

判断一个数是否是素数

作者: gattonero | 来源:发表于2019-03-29 00:25 被阅读0次

    问题

    如题

    思路

    首先太暴力的就不谈,会折寿,有一个强伪证的算法(strong liar)Miller Rabin Test,思路是这样(以下p代表某一个大于2的素数),找到判断素数的必要条件,将多个条件组合起来就能得到近似充分的判断素数条件

    两个引理说一下,首先是二次探测定理:如果x2≡1(mod p),那么x≡±1(mod p),或者说不存在模p等于1下的非平凡平方根(证明:p只有1和p两个因子的情况下,(x+1)(x-1)≡0(mod p)只可能有x-1=0或x+1=p)

    然后是费马小定理,a和p互质(gcd(a,p)=1)时,ap-1≡1(mod p)

    好了开始,对于要判断的数P,任取2-p内的数a,这里我们方便起见取a=2
    根据上述条件,p-1一定是偶数,可以分解成2r*d的形式,所以对于a2^r*d ≡1(mod p),也就是(a2^(r-1)*d )2≡1(mod p),设x(n) = (a(2^n*d)) mod p,那么目前的情况是,我们仅有平凡平方根x(r-1)≡±1(mod p)

    这里如果x(r-1)≡1(mod p),问题就变得可递归了,因为接下来的方程是a2^(r-1)*d≡1(mod p),然后我们可以继续往下解xn-1,xn-2...
    如果是x(r-1)≡-1(mod p),那么问题就更简单了,因为接下来的解不确定,不用往下推了

    所以从上往下推我们可以看到,对于函数x的序列,x(r)=1是一定的,而且如果x(t)=-1,那么x(t+1)到x(r)一定都是1,也就是说,对于序列中的数只要判断两个条件即可:
    1.1之前的数一定是1或-1
    2.最后一个数一定是1

    解决

        public boolean sPrime_RobinMiller(long p) {
            long[] ar = new long[]{2, 3, 5, 7, 11};//if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
    
            if (p < 4) return p > 1;
            if (p == 5 || p == 7 || p == 11) return true;//a<p-1
    
            for (long a : ar) {
                long p1 = p - 1, u = p1 & -p1, d = p1 / u, cur = quickPow(a, d, p), prev = cur;
                while (u > 0) {
                    cur = prev * prev % p;
                    if (cur == 1 && prev != 1 && prev != p1)
                        return false;//序列中,1之前的数一定是1或者-1
                    prev = cur;
                    u >>= 1;
                }
    
                if (cur != 1)
                    return false;//序列的最后一个数一定是1
            }
    
            return true;//all passed
        }
    
        private long quickPow(long a, long b, long c) {
            long res = 1;
            for (; b > 0; b >>= 1, a = a*a%c)
                if ((b & 1) == 1) {
                    res = res * a % c;
                }
            return res;
        }
    

    Tips

    • 取a=2,3,5,7,11,对于int范围内所有数(小于2147483648的所有数)都可以判断出结果,注意这时需要对3,5,7,11单独判断一遍,因为前提条件是gcd(a,p)=1
    • 并不是所有数据类型取long就能判断出长整型范围内的数据了,因为快速幂中需要计算2d mod p,其中a*a是有可能溢出的

    Ref

    https://oi-wiki.org/math/prime/
    https://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C

    相关文章

      网友评论

          本文标题:判断一个数是否是素数

          本文链接:https://www.haomeiwen.com/subject/mdzhbqtx.html