质数筛
大约 2 分钟
给出2种低时间复杂度快速筛选质数的方法
埃氏筛
埃氏筛，即 埃拉托斯特尼筛法，时间复杂度为 O(nlog(logn))，算法详情可参见wiki百科：埃拉托斯特尼筛法
public class AceSifter {
/*
* 返回 <= n 的所有质数
*
* @param n 上界
*/
private static List<Integer> aceSifter(int n) {
// 质数表
List<Integer> primes = new ArrayList<>();
// flag[i] = true: i为质数
boolean[] flag = new boolean[n + 1];
Arrays.fill(flag, true);
// 0、1 不是质数
flag[0] = flag[1] = false;
// 将合数置为false
for (int i = 2; i <= n; i++) {
if (flag[i]) {
// 注: j >= 0作用: 避免溢出
for (int j = i * i; j >= 0 && j <= n; j += i) {
// 此处可加 if (flag[i]) 判断, 也可不加
flag[j] = false;
}
primes.add(i);
}
}
return primes;
}
public static void main(String[] args) {
List<Integer> primes = aceSifter(110);
System.out.println(primes);
}
}
欧拉筛/线性筛
欧拉筛，又名线性筛，时间复杂度为 O(n)，算法详情可参考: 欧拉筛
public class EulerSifter {
/**
* 返回 <= n 的所有质数<br/>
* @param n 上界
*/
private static List<Integer> eulerSifter(int n) {
// 质数表
List<Integer> primes = new ArrayList<>();
// flag[i] = true: i为质数
boolean[] flag = new boolean[n + 1];
Arrays.fill(flag, true);
// 0、1 不是质数
flag[0] = flag[1] = false;
// 2 是质数
flag[2] = true;
for (int i = 2; i <= n; i++) {
// 若i是「质数」，添加至质数表
if (flag[i]) {
primes.add(i);
}
// l是i的最小质因数，将 <=l(i的最小质因数)的质数与i相乘，并标记为false
for (int l : primes) {
if (i * l > n) {
break;
}
flag[i * l] = false;
if (i % l == 0) {
break;
}
}
}
return primes;
}
public static void main(String[] args) {
List<Integer> primes = eulerSifter(110);
System.out.println(primes);
}
}