高效计算素数个数

初级解法

public int countprimes(int n){
    int count=0;
    for(int i=2;i<n;++i){
        if(isPrime(i)) count++;    
    }
    return count;
}
public boolean isPrime(int n){
    for(int i=2;i<n;++i){
        if(n%i==0) return false;
    }
    return true;
}

该解法时间复杂度

对isPrime优化

public boolean isPrime(int n){
    for(int i=2;i*i<=n;++i){
        if(n%i==0) return false;
    }
    return true;
}

因为多余的循环部分不过是 A * B 变为B * A，时间复杂度优化为

记录已经被计算的部分减少时间复杂度

public int countprimes(int n){
    boolean[] rem=new boolean[n+1];
    Arrays.fill(rem,true);
    for(int i=2;i*i<n;++i){
        if(rem[i]) {
            for(int k=i*i;k<n;k+=i){
                rem[k]=false;
            }
        }
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;
    }
    return count;
}

因为任何数的倍数都不可能是素数，因此可以进行如上操作。同时内层判断也进行了优化，例如4的倍数一定已经被2的倍数计算过了，存在冗余循环。