找质数

刷题

题目：找出自然数 n 范围之内的质数

/**
 * 埃氏筛与欧拉筛的比较
 * 找出自然数 n 范围之内的质数
 */
public class 找质数 {
    private static final int MAX_LENGTH_CHECK = 100000001;  // 亿
    private static final int MAX_LENGTH_PRIMELIST = 10000000;// 千万
    private static boolean[] check = new boolean[MAX_LENGTH_CHECK];
    private static int[] primeList = new int[MAX_LENGTH_PRIMELIST];
    /**
     * 埃氏筛：要得到自然数 n 以内的全部素数，必须把不大于 根号n 的所有素数的倍数剔除，剩下的就是素数。
     * 解法：先用2去筛，把2留下，2的倍数剔除；再用下一个质数3筛，把3留下，3的倍数剔除掉，不断重复……
     *
     * 时间复杂度：O(nloglogn)
     */
    private static void Eratosthenes(int num) {
        int count = 0;
        for (int i = 2; i <= num; i++) {
            // 当 i 不是要被剔除的数时，把 i 留下
            if (!check[i]) {
                primeList[count++] = i;
            }
            // 剔除 i 的倍数
            for (int j = i + i; j <= num; j += i) {
                check[j] = true;    //  标记为剔除
            }
        }
    }
    /**
     * 欧拉筛：保证每个合数只会被它最小的质因数筛掉，时间复杂度降低到O(n)
     * 解法：每个数都去乘当前素数表里已有的数，当 i 是合数时且 i%primeList[j]==0 时，只能乘第一个素数
     */
    private static void Euler(int num) {
        int count = 0;
        for (int i = 2; i <= num; i++) {
            if (!check[i]) {
                primeList[count++] = i;
            }
            for (int j = 0; j < count; j++) {
                // 超过范围后跳出
                if (i * primeList[j] > num) {
                    break;
                }
                check[i * primeList[j]] = true;
                // 保证每个合数只会被它最小的质因子筛掉
                if (i % primeList[j] == 0) {
                    break;
                }
            }
        }
    }
    public static void main(String[] args) throws InterruptedException {
        int n = 100000000;
        long start,end;
        start = System.currentTimeMillis();
        Euler(n);
        end = System.currentTimeMillis();
        System.out.println("亿级别数量：欧拉筛，耗时：" + (end - start) + " ms");
        Arrays.fill(check, false);
        Arrays.fill(primeList, 0);
        start = System.currentTimeMillis();
        Eratosthenes(n);
        end = System.currentTimeMillis();
        System.out.println("亿级别数量：埃氏筛，耗时：" + (end - start) + " ms");
    }
}

结果如下：

亿级别数量：欧拉筛，耗时：1109 ms
亿级别数量：埃氏筛，耗时：13135 ms