素数筛 Prime sieve

素数又称质数：一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定 1 既不是质数也不是合数）。

素数筛方法主要有三种：

素数的判定（素数筛）
普通线性筛（埃氏筛法 / 埃拉托斯特尼（Eratosthenes）筛法）
优化后的线性筛（欧拉筛法 / 欧拉函数（Euler）筛）

寻找素数，二重循环暴力查找，复杂度O(n^2)，通过循环中只判断到根号 n 可以优化一些。
在数论中，埃氏筛法，O(n loglogn) 的算法，而数据范围达到 1e7 时也不理想，欧拉筛法，O(n) 的线性筛法。

一、素数的判定

暴力枚举，枚举 2 ~ √n 所有数，用 n 去试着除以，若有能整除的 n 为合数，若都不能整除，n 就是质数。
时间复杂度：O（√n）

boolean isPrime(int x){	
	if(x < 2) return false; // 0 和 1 既不是质数也不是合数 
	for(int i = 2; i * i <= x; i++)
		if(x % i == 0) return false;
	return true;
}

二、埃氏筛法

埃拉托斯特尼： 古希腊数学家、地理学家、历史学家、诗人、天文学家，主要贡献设计出经纬度系统，计算出地球的直径。
埃拉托斯特尼筛法，简称埃氏筛法，寻找质数的方法。

原理：要得到自然数 n 以内的全部素数，必须把不大于根号 n 的所有素数的倍数剔除，剩下的就是素数。

先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉；把 3 留下，把 3 的倍数剔除掉；…。

时间复杂度：O（n loglogn )

三、欧拉筛法

时间复杂度：O(n)

埃式筛法，同一个数字也许会被筛选多次，比如 6 先被 2 筛选一次，再被 3 筛选一次。欧拉筛法就是在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

用一条语句 if(i % prime[j] == 0) break; 避免了重复筛选的发生。

import java.util.Arrays;

public class Prime {
    /**
     * 埃拉托斯特尼筛法 VS 欧拉筛法（更优化）
   */
    private static final int MAX_LENGTH_CHECK = 100000000; // 亿
    private static final int MAX_LENGTH_PRIMES = 10000000; // 千万
    private static boolean[] check = new boolean[MAX_LENGTH_CHECK]; // 存储标记
    private static int[] primes = new int[MAX_LENGTH_PRIMES]; // 存储素数
    /**
     * 埃拉托斯特尼筛法（简称埃氏筛或爱氏筛）：要得到自然数 n 以内的全部素数，必须把不大于 根号 n 的所有素数的倍数剔除，剩下的就是素数。
     * 例如：给出要筛数值的范围 n，找出以内的素数。
     * 解法：先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉；再用下一个质数，也就是 3 筛，把 3留下，把3的倍数剔除掉；不断重复下去......。
     * <p>
     * 时间复杂度：O(nloglogn)
     * 不足之处：6 在 i = 2 时被标记，而在 i = 3 时，又被标记了一次。存在重复标记。
     */
    private static void Eratosthenes(int n) {
        int count = 0;
        for (int i = 2; i <= n; i++) {
            // 当 i 不是被剔除的数时，将 i 留下
            if (!check[i])  primes[count++] = i;
            // 剔除 i 的倍数
            for (int j = i + i; j <= n; j += i) check[j] = true;
            // for (int j = i * i; j <= n; j += i) { // 2 到 i - 1 倍已经筛过，10 万级 i * i 会越界。
        }
    }

    /**
     * 欧拉筛法：保证每个合数只会被它的最小质因数筛掉，时间复杂度降低到 O(n)。
     * 每一个数都去乘以当前素数表里面已有的数，当 i 是合数，且 i % primes[j] == 0 时，只能乘以第一个素数 2
     */
    private static void Euler(int n) {
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (!check[i]) primes[count++] = i;
            // 每一个数都去乘以当前素数表里面已有的数，如果 i 是合数，且 i % primes[j] == 0，那么它只能乘以第一个素数 2
            // 如：2×2、3×(2、3)、4×(2)、5×(2、3、5)、6×(2)、7×(2、3、5、7)、8×(2)、9×(2、3)、10×(2)
            for (int j = 0; j < count; j++) {
                // 过大的时候跳出
                if (i * primes[j] > n) break;
                check[i * primes[j]] = true; // 合数
                // 如果 i 是一个合数，而且 i % primes[j] == 0
                // 保证了每个合数只会被它的最小素因子筛掉
                if (i % primes[j] == 0) break;
            }
        }
    }

    public static void main(String[] args) {
        int n = 100000; // 十万
        long start = System.currentTimeMillis();
        Eratosthenes(n);
        long end = System.currentTimeMillis();
        System.out.println("十万级别数量：埃氏筛，耗时：" + (end - start) + " ms");

        Arrays.fill(check, false);
        Arrays.fill(primes, 0);

        start = System.currentTimeMillis();
        Euler(n);
        end = System.currentTimeMillis();
        System.out.println("十万级别数量：欧拉筛法，耗时：" + (end - start) + " ms");
    }
}

四、六倍原理

除了 2 和 3 以外，其余素数都与 6 的倍数相邻，也就是也就是说大于 3 的质数一定满足 6n + 1或 6n − 1。

boolean isprime(int n){
    if (n == 1) return false;
    else if (n == 2 || n == 3) return true;
    // 不满足六倍原理，一定不是素数
    else if (n % 6 != 1 && n % 6 != 5) return false;
    // 只判断 6 倍的邻数
    for (int i = 5; i <= sqrt(n); i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}