求素数的三种方法

1175. 质数排列

204. 计数质数

暴力

private List<Integer> getPrime(int n) {
    List<Integer> list = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        boolean ok = true;
        // 注意：j * j <= i 即可
        for (int j = 2; j * j <= i && ok; j++) {
            if (i % j == 0) ok = false;
        }
        if (ok) list.add(i);
    }
    return list;
}

埃氏筛法 (推荐)

整个过程如图所示：

x
private List<Integer> getPrime(int n) {
    List<Integer> list = new ArrayList<>();
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) continue;
        list.add(i);
        for (int j = i + i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
    return list;
}

欧拉筛法

private List<Integer> getPrime(int n) {
    List<Integer> list = new ArrayList<>();
    boolean[] vis = new boolean[n + 1];
    for (int i = 2; i <= n; i++) {
        // 如果没有访问过，一定是素数
        if (!vis[i]) {
            list.add(i);
            vis[i] = true;
        }
        for (int j = 0; j < list.size(); j++) {
            int cur = list.get(j);
            if (i * cur > n) break;
            vis[i * cur] = true;
            if (i % cur == 0) break;
        }
    }
    return list;
}