素数算法

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

一. 判断质数的基本算法

根据素数的定义，要判断$x$($x >= 2$)是否为素数，只需要逐一判断该数能否被从2到x-1的数整除即可。核心代码如下

boolean isPrime(int x) {
    if(x == 1) {
        return false; // 1不是素数
    } else if(x == 2) {
        return true; // 2是唯一的偶数质数
    }
    for(int i = 2; i < x; ++i) {
        if(x % i == 0) {
            return false;
        }
    }
    return true;
}

上述暴力算法还存在一定的优化空间，实际上我们在循环中只需要判断到$\sqrt x$即可。优化版本如下

boolean isPrime(int x) {
    if(x == 1) {
        return false; // 1不是素数
    } else if(x == 2) {
        return true; // 2是唯一的偶数质数
    }
    for(int i = 2; i < (int)(Math.sqrt(x) + 1); ++i) {
        if(x % i == 0) {
            return false;
        }
    }
    return true;
}

这种方法只适合小规模数据，当数据过大或需要判断某个范围内的质数时，这种方法就很难达到我们所需要的性能要求。

二、 埃氏筛

埃氏筛的核心思想如下：从2开始删去素数本身倍数，向后找到的第一个数字一定是素数。埃氏筛的时间复杂度为$O(NloglogN)$，相比暴力算法，其不仅在效率上得到了极大提高，并且可以用于筛选一定范围内的质数。核心代码如下

// 假设筛选范围为(1, n)
List<Integer> getAllPrimes(int n) {
    boolean[] isNotPrime = new boolean[n + 1]; // 创建的数组默认值为false，故设置为isNotPrime可以免去将数组初始化为true的过程
    List<Integer> res = new ArrayList<>(); // 存放找到的所有素数
    isNotPrime[0] = true;
    isNotPrime[1] = true;
    for(int i = 2; i <= n; ++i) {
        if(!isNotPrime[i]) {
            res.add(i);
            // 如果是素数，则需要将素数的倍数标记为合数
            int j = i * 2;
            while(j <= n) {
                isNotPrime[j] = true;
                j += i;
            }
        }
    }
    return res;
}

三、 线性筛（欧拉筛）

尽管埃氏筛本身的时间复杂度已经足够优秀，但仍然有优化空间。比如对于数字12，其为质数2的倍数，也是质数3的倍数，也就是埃氏筛中，它会被筛掉两次，浪费了时间。那么有没有办法能够避免这种重复的筛选呢？

对于任何一个合数，都能够写成一个素数乘以一个数，也就是说对于任何一个合数，都拥有一个最小质因数，欧拉筛就是用这个最小质因数用来判断什么时候不需要再继续筛下去。核心代码如下

// 假设筛选范围为(1, n)
List<Integer> getAllPrimes(int n) {
    boolean[] isNotPrime = new boolean[n + 1]; // 创建的数组默认值为false，故设置为isNotPrime可以免去将数组初始化为true的过程
    List<Integer> res = new ArrayList<>(); // 存放找到的所有素数
    isNotPrime[0] = true;
    isNotPrime[1] = true;
    for(int i = 2; i <= n; ++i) {
        if(!isNotPrime[i]) {
            res.add(i);
        }
        
        for(int j = 0; j < res.size() && res.get(j) * i <= n; ++j) {
            isNotPrime[res.get(j) * i] = true;
            // 埃氏筛优化的核心
            if(i % res.get(j) == 0) {
                break;
            }
        }
    }
    return res;
}