素数的定义:如果一个大于1的正整数n只有1和它本身这两个因子,那么n是素数,否则n是合数。1不是素数也不是合数。

求素数的几种方法,复杂度从大到小:

试除法

对于一个整数n,如果区间[2, \sqrt(n)]内不存在n的因子,那么n是质数。因为一个数的因子中除了其算术平方根外,都是成对出现的,且不可能存在两个大于\sqrt(n)的因子(显而易见)。那么使用试除法判断一个素数最多需要O(\sqrt(n))的复杂度,判断n个就是O(n\sqrt{n})

埃式筛法

欲判断[2, n]内的数的素性,从前往后一个一个扫描,若当前数未做合数标记,那么它就是质数,比如一开始就能判断2和3都是质数;每扫描到一个质数p,那么它的任何不大于n的倍数都是合数,就把2p, 3p, 4p,,,一直到n为止这些数都标记为质数。时间复杂度略大于O(n)
因为在标记的时候仅是在扫描到质数时才开始标记工作,若对于[1, n]内每一个数都进行如上标记,那么时间复杂度为O(nlogn)。即\sum_{i=1}^{n}n/i \approx nlogn.

欧拉筛

线性处理素数的方法,利用唯一分解定理得到一个性质:每个合数总会有一个最小的质因数,利用这个最小的质因数来标记该合数,每个数只会被标记1次,时间复杂度为O(n)
步骤:同样是从前往后一个个扫描,若扫描到的数未被标记,它就是质数,并将该质数p存进质数数组prime里,用cnt来记录此时已经得到多少个素数,prime数组里的质数是从小到大排列好的。再扫描prime数组,对于那些小于p的

Miller-Rabin素性测试

米勒罗宾素性测试可以在较短的时间内判断出一个大整数的素性。比如现在想判断一个长度100位的整数是否为素数,使用上面的几种方法都不能在短时间内得到结果,因此很难得到一个确定的结果来判断该整数是否为素数。可以考虑对整数进行素性测试,具体需要用到下面两个定理。
费马小定理:若n为质数,则对于任意整数a,有a^{n-1}(\%n)=1,但是当该式成立时,n不一定是质数;当a^{n-1}(\%n)的结果不为1是,n一定是合数。可以以此来在一定程度上测试一个数的素性。(费马小定理推广自欧拉定理)

二次探测定理:若n为质数,则方程x^2(\%n)=1的解只有1和n-1.对方程进行变形:x^2-1=an, (x+1)(x-1)=an,n为素数所以没有其余的质因子,方程成立的情况只能是x=1或者x=n-1。这里的x都是经过对n取模后的值。

米勒罗宾素性测试步骤为:每一轮测试中,选取一个测试因子a,先计算a^{n-1}\%n的值是否为1,不是1的话测试不通过,n一定为合数;否则继续使用二次探测定理进行测试,对n-1进行开方,若开方得到的值为n-1,测试通过,n可能为质数;若开方得到的值为1,那么可以继续开方;若得到了其它值,那么测试不通过,n一定是合数。

在代码实现中,步骤和上述是反着来的:先对n-1不断开方,即表示成n-1=2^{s}·d的形式,d为奇数,s大于1。
然后先计算2^d\%n是否为1或n-1,若是,则测试通过;否则,一定是在开方过程中有某一步模n出现了其它值,就开始对该值进行平方取模操作。若先得到n-1,则测试通过;若先得到1,则说明存在x使得x^2=1的解不是1也不是n-1,那么测试不通过,n一定为合数。若已经平方过s次后还未退出上述循环,也就是说此时计算的值已经达到了a^{n-1},那么此时不论结果是1还是n-1,n都一定是合数。
因为计算过程中要用到高精度,时间复杂度为O((lgn)^3)
python代码如下:

def pmod(a, b, c):
    if (a==0):
        return 0
    ans = 1
    while b>0:
        if (b&1):
            ans = ans*a%c
        b >>= 1
        a = a*a%c
    return ans

def check(a, n):
    d = n-1
    s = 0
    while (d&1)==0:
        d >>= 1
        s+=1
    t = pmod(a, d, n)

    if t==1 or t==n-1:
        return True

    while (s>0):
        s -= 1

        if (t==n-1):
            return True
        if t==1:
            return False
        t = t*t%n

    return False

def solve(n):
    if (n<1000):
        f = 0
        for i in range(2, n):
            if n%i==0:
                f = 1
                break
        if f==0:
            print("Yes")
        else:
            print("No")
        return 0

    for a in range(16350, 16351):
        if False==check(a, n):
            print("No")
            return 0
    print("Yes")
    return 0

while True:
    try:
        s = input()
        solve(int(s))
    except EOFError:
        break

Java代码,C++就先暂时放着吧...有时间整理一下大整数再写

import java.math.BigInteger;
import java.util.Scanner;
public class primeJudge{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            if ( false==isprime.primejudge(new BigInteger(scanner.nextLine())) )   System.out.println("No");
            else    System.out.println("Yes");
        }
        scanner.close();
    }
};

class isprime {

    public static boolean primejudge(BigInteger n) {
        if (n.subtract(new BigInteger("1000000")).signum() <= 0 ) {
            int tmp = Integer.valueOf(n.toString());
            for (int i=2; i*i<=tmp; i++) if (tmp%i==0)
                return false;
            return true;
        }
        for (int a = 16350; a<=16360; a++) {
            if (Miller_Rabin(n, new BigInteger(String.valueOf(a)))==false)
                return false;
        }
        return true;
    }
    // 快速幂 a^b%m
    private static BigInteger qpow(BigInteger a, BigInteger b, BigInteger m, BigInteger yi, BigInteger er) {
        if (b.signum()==0)  return new BigInteger("0");
        BigInteger ans = new BigInteger("1");
        while (b.signum()==1) {
            if (b.mod(er).equals(yi))    ans = (ans.multiply(a)).mod(m);
            b = b.divide(er);
            a = (a.multiply(a)).mod(m);
        }
        return ans;
    }
    // 一次米勒罗宾测试
    private static boolean Miller_Rabin(BigInteger n, BigInteger a) {
        BigInteger d = new BigInteger("0");
        BigInteger yi = new BigInteger("1");
        BigInteger er = new BigInteger("2");
        BigInteger tmp = n.subtract(yi);
        d = n.subtract(yi);
        int s = 0;
        //233System.out.println(d.mod(er).toString());
        while (d.mod(er).equals(yi)==false) {
            s++;
            d = d.divide(er);
        }
        BigInteger t = qpow(a, d, n, yi, er);
        if (t.equals(yi) || t.equals(tmp)) return true;
        while (s>0) {
            s -= 1;
            if (t.equals(tmp))  return true;
            if (t.equals(yi))   return false;
            t = t.multiply(t).mod(n);
        }
        return false;
    }
};
// 大概20次米勒罗宾测试消耗1000ms

代码中我选取的测试因子a是从16350开始的连续几个数,选了几个数就是进行几轮测试,测试出错的改率为\frac{1}{2^{k}},k为测试次数。
我瞎选的这个数出错率还是挺低的
题目链接:
水题
若干测试数据,每行一个一百位以内的正整数,判断是否为素数。("Yes" "No")
数论一·Miller-Rabin质数测试
第一行给出测试数据个数,接下来每行一个long long范围内的数,测试是否为素数。


0 条评论

发表评论

邮箱地址不会被公开。