Java素数测试

BigInteger中的素数测试方法

MillerRabin素数测试，时间复杂度O(klog³n)，k为测试次数，n是测试的数字

---

boolean primeToCertainty(int certainty, Random random) （关键方法，不可调用）

MillerRabin素数测试的测试次数为(certainty+1)/2

测试数字的长度 < 100：

使用MillerRabin素数测试，测试次数最大为50。

测试数字的长度 >= 100：

使用MillerRabin+LucasLehmer共同测试

boolean primeToCertainty(int certainty, Random random) {
    int rounds = 0;
    int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

    // The relationship between the certainty and the number of rounds
    // we perform is given in the draft standard ANSI X9.80, "PRIME
    // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
    int sizeInBits = this.bitLength();
    if (sizeInBits < 100) {
        rounds = 50;
        rounds = n < rounds ? n : rounds;
        return passesMillerRabin(rounds, random);
    }

    if (sizeInBits < 256) {
           rounds = 27;
    } else if (sizeInBits < 512) {
        rounds = 15;
    } else if (sizeInBits < 768) {
        rounds = 8;
    } else if (sizeInBits < 1024) {
        rounds = 4;
    } else {
        rounds = 2;
    }
    rounds = n < rounds ? n : rounds;

    return passesMillerRabin(rounds, random) && passesLucasLehmer();
}

public boolean isProbablePrime(int certainty) （可调用）

参数certainty，若<0，直接返回true

特判2,2之外的偶数以及1。

其他使用primeToCertainty测试。

• 注意：MillerRabin素数测试的测试次数为(certainty+1)/2

kuangbin模板上面MillerRabin算法推荐测试次数为8-10次，对应参数为15-19。

• 注意：只有数字长度<100，才会只使用MillerRabin测试，且最多测试50次。

public boolean isProbablePrime(int certainty) {
    if (certainty <= 0)
        return true;
    BigInteger w = this.abs();
    if (w.equals(TWO))
        return true;
    if (!w.testBit(0) || w.equals(ONE))
        return false;

    return w.primeToCertainty(certainty, null);
}

public BigInteger nextProbablePrime() （可调用）

内部对素数的判定，不是特判，就是使用primeToCertainty测试。

nextProbablePrime()找下一个素数是通过+一个值来寻找。每得到一个新值，测试一次。

该数字<95，+2。

>=95，使用BitSieve筛选。（BitSieve无法由用户创建）。先确定查询长度，然后再加值。具体地我也看不懂。

• 但是该方法不会跳过任何素数

public BigInteger nextProbablePrime() {
    if (this.signum < 0)
        throw new ArithmeticException("start < 0: " + this);

    // Handle trivial cases
    if ((this.signum == 0) || this.equals(ONE))
        return TWO;

    BigInteger result = this.add(ONE);

    // Fastpath for small numbers
    if (result.bitLength() < SMALL_PRIME_THRESHOLD) {

        // Ensure an odd number
        if (!result.testBit(0))
            result = result.add(ONE);

        while (true) {
            // Do cheap "pre-test" if applicable
            if (result.bitLength() > 6) {
                long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
                if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
                    (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
                    (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                    result = result.add(TWO);
                    continue; // Candidate is composite; try another
                }
            }

            // All candidates of bitLength 2 and 3 are prime by this point
            if (result.bitLength() < 4)
                return result;

            // The expensive test
            if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                return result;

            result = result.add(TWO);
        }
    }
    // Start at previous even number
    if (result.testBit(0))
        result = result.subtract(ONE);

    // Looking for the next large prime
    int searchLen = getPrimeSearchLen(result.bitLength());

    while (true) {
        BitSieve searchSieve = new BitSieve(result, searchLen);
        BigInteger candidate = searchSieve.retrieve(result,
                                                DEFAULT_PRIME_CERTAINTY, null);
        if (candidate != null)
            return candidate;
        result = result.add(BigInteger.valueOf(2 * searchLen));
    }
}

测试isProbablePrime

hdu 2138 MillerRabin模板题

import java.io.BufferedInputStream;
import java.io.InputStream;
import java.math.BigInteger;
import java.util.*;

public class Main {

    private static Scanner scan = new Scanner(new BufferedInputStream(System.in));
    public static void main(String[] args) {
        while(scan.hasNext()) {
            int n = scan.nextInt();
            int ans = 0;
            for (int i = 0; i < n; ++ i) {
                int x = scan.nextInt();
                if(BigInteger.valueOf(x).isProbablePrime(15)) ++ ans;
            }
            System.out.println(ans);
        }
    }
}