Eratosthenes

Calculate the number of the prime numbers in a given range N.

    public static int eratosthenes (int n){
        boolean[] isNotPrime = new boolean[n]; //false represents a prime number
        int count = 0;
        for(int i=2; i<n; i++){
            if(!isNotPrime[i]){ //is prime number
                count++;
                //for(int j=2*i; j<n; j+=i){//j是合数标记位置 j+=i因为要从2*i 3*i 4*i 逐渐递增。但是在这个循环不好直接修改i
                for(int j=i*i; j<n; j+=i){//无需从2*i开始，因为如果是2*i的话，比如i=2的时候会计算2*4，i=4的时候也会从2*4开始，这样就重复了
                    isNotPrime[j] = true; //标记这些合数 label composite number
                }
            }
        }
        return count;
    }