质数相关

---

埃氏筛

判断质数

// 判断质数
public boolean ehrlich(int n) {
    // 初始化所有值为 true，认为都是质数
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    // 特殊处理：0 和 1 不是质
    isPrime[0] = false;
    isPrime[1] = false;

    // 埃氏筛
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            // 如果 i 是质数，则标记和数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime[n];
}

质数打表

// 质数打表
public void ehrlich(int n) {
    // 初始化所有值为 true，认为都是质数
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    // 特殊处理：0 和 1 不是质
    isPrime[0] = false;
    isPrime[1] = false;

    // 埃氏筛
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            // 如果 i 是质数，则标记和数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 质数打表
    for (int i = 0; i < isPrime.length; i++) {
        if (isPrime[i]) {
            System.out.println(i);
        }
    }
}