计算范围内的质数个数,尽可能避免循环次数｜Java 刷题打卡

public int countPrimes(int n) {
    int total = 0;
    for (int i = 2; i < n; i++) {
        int j=2;
        for (j = 2; j < i; j++) {
            if (i % j == 0) {
                break;
            }
        }
        if (j == i) {
            total++;
        }
    }
    return total;
}

public int countPrimes(int n) {
    int total = 0;
    for (int i = 2; i < n; i++) {
        boolean flag = false;
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                flag=true;
                break;
            }
        }
        if (!flag) {
            total++;
        }
    }
    return total;
}

public int countPrimes2(int n) {
    int total = 0;
    //构造同等长度的状态位数组， 默认false表示质数
    boolean[] primes = new boolean[n];
    for (int i = 2; i < n; i++) {
        if (!primes[i]) {
            total++;
            for (int j = 2 * i; j < n; j += i) {
                primes[j] = true;
            }
        }
    }
    return total;
}

public int countPrimes3(int n) {
    int total = 0;
    //构造同等长度的状态位数组， 默认false表示质数
    boolean[] primes = new boolean[n];
    for (int i = 2; i < n; i++) {
        if (!primes[i]) {
            total++;
            if ((long)i * i >= n) {
                continue;
            }
            for (int j = i * i; j < n; j += i) {
                //System.out.println("index="+j+"i="+i);
                primes[j] = true;
            }
        }
    }
    return total;
}