学步园

 

 

 素数基础： 1不是素数；除了2以外的所有偶数都是合数。
 1朴素判别素数
 判断一个数n是不是素数，只要判断从2到sqrt(n)的数是否能整除n，如果能则不是素数，否则就是素数。

 2朴素筛选法素数
 去掉当前素数的倍数（因为它们都是合数）

private final static int VAL = 10000000;
    static int primeLen;
    static int[] primeArr = new int[VAL];
    static boolean[] isPrimeArr = new boolean[VAL];

    /**
    * 朴素筛法
    */
    public static void initPrimeArr() {
        Arrays.fill(isPrimeArr, false);
        isPrimeArr[1] = true;
        isPrimeArr[0] = true;
        for (int i = 2; i < VAL; i++) {
            if (!isPrimeArr[i]) {
                for (int j = i + i; j < VAL; j += i) {
                    isPrimeArr[j] = true;
                }
            }
        }
        primeLen = 0;
        for (int i = 0; i < VAL; i++) {
            if (!isPrimeArr[i]) {
                primeArr[primeLen++] = i;
            }
        }
    }

 

 3线性筛法
 利用每个合数必有一个最小质因数，每个合数仅被它的最小素因数筛去正好一次。

 

    private final static int VAL = 10000000;
    static int primeLen;
    static int[] primeArr = new int[VAL];
    static boolean[] isPrimeArr = new boolean[VAL];

    /**
     * 线性筛选素数
     */
    public static void initPrimeArr() {
        Arrays.fill(isPrimeArr, false);
        primeLen = 0;
        for (int i = 2; i < VAL; i++) {
            if (!isPrimeArr[i]) {
                primeArr[primeLen++] = i;
            }
            for (int j = 0; (j < primeLen) && (i * primeArr[j] < VAL); j++) {
                isPrimeArr[i * primeArr[j]] = true;
                if (i % primeArr[j] == 0) {
                    break;
                }
            }
        }
    }

 先剔除除2以外的所有偶数，在根据剔除最小素因数的合数的方法，如下：

    private final static int VAL = 10000000;
    static int primeLen;
    static int[] primeArr = new int[VAL];
    static boolean[] isPrimeArr = new boolean[VAL];

    /**
     * 线性筛选素数
*/
    public static void initPrimeArr() {
        Arrays.fill(isPrimeArr, false);
        primeLen = 0;
        primeArr[primeLen++] = 2;
        for (int i = 4; i < VAL; i += 2) {
            isPrimeArr[i] = true;
        }
        for (int i = 3; i < VAL; i += 2) {
            if (!isPrimeArr[i]) {
                primeArr[primeLen++] = i;
            }
            for (int j = 0; (j < primeLen) && (i * primeArr[j] < VAL); j++) {
                isPrimeArr[i * primeArr[j]] = true;
                if (i % primeArr[j] == 0) {
                    break;
                }
            }
        }
    }

 4求区间素数

static int intervalPrimeLen;
    static int[] intervalPrimeArr = new int[VAL];
    static boolean[] isIntervalPrimeArr = new boolean[VAL];

    public static void findIntervalPrimeArr(int L, int R) {
        int temp = (int) Math.sqrt(1.0 * R);
        int interval = R - L + 1;
        Arrays.fill(isIntervalPrimeArr, true);
        for (int i = 0, j; (i < primeLen) && (primeArr[i] <= temp); i++) {
            if ((j = L / primeArr[i] * primeArr[i]) < L) {
                j += primeArr[i];
            }
            if (j < primeArr[i] * primeArr[i]) {
                j = primeArr[i] * primeArr[i];
            }
            for (; j <= R; j += primeArr[i]) {
                isIntervalPrimeArr[j - L] = false;
            }
        }
        intervalPrimeLen = 0;
        for (int i = 0; i < interval; i++) {
            if (isIntervalPrimeArr[i] && (i + L > 1)) {
                intervalPrimeArr[intervalPrimeLen++] = i + L;
            }
        }
    }

    public static void findIntervalPrimeArr2(int L, int R) {
        int interval = R - L + 1;
        int temp = (int) Math.sqrt(1.0 * R);
        Arrays.fill(isIntervalPrimeArr, false);
        // 把偶数直接去掉，开始是L是否为奇偶数
        for (int i = (L & 1); i <= interval; i += 2) {
            isIntervalPrimeArr[i] = true;
        }
        for (int i = 3, j; i <= temp; i += 2) {
            if ((i > L) && isIntervalPrimeArr[i - L]) {
                continue;
            }
            j = (L / i) * i;
            if (j < L) {
                j += i;
            }
            if (j == i) {
                j += i;
            }
            j -= L;
            for (; j < interval; j += i) {
                isIntervalPrimeArr[j] = true;
            }
        }
        if (L <= 1) {
            isIntervalPrimeArr[1 - L] = true;
        }
        if (L <= 2) {
            isIntervalPrimeArr[2 - L] = false;
        }
        intervalPrimeLen = 0;
        for (int i = 0; i < interval; i++) {
            if (!isIntervalPrimeArr[i]) {
                intervalPrimeArr[intervalPrimeLen++] = i + L;
            }
        }
    }

5某个数的最小素因数

    static int intervalPrimeLen;
    static int[] intervalPrimeArr = new int[VAL];
    static int[] primeFactorArr = new int[VAL];

    public static void mkPrimeAndFactor() {
        Arrays.fill(primeFactorArr, 0);
        primeFactorArr[0] = 1;
        primeFactorArr[1] = 1;
        primeLen = 0;
        for (int i = 2; i < VAL; i++) {
            if (primeFactorArr[i] == 0) {
                primeArr[primeLen++] = i;
                primeFactorArr[i] = i;
            }
            for (int j = 0; (j < primeLen)
                    && (i * primeArr[j] < VAL)
                    && (primeArr[j] <= primeFactorArr[i] || primeFactorArr[i] == 0); j++) {
                primeFactorArr[i * primeArr[j]] = primeArr[j];
                if (i % primeArr[j] == 0) {
                    break;
                }
            }
        }
    }

 6大素数判定

米勒罗宾算法

Java中的大数BigInteger中的isProbableprime(int certainty )