埃氏筛选法求解质数

一、埃氏筛选法
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
要得到自然数n以内的全部素数，必须把不大于 的所有素数的倍数剔除，剩下的就是素数。
给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。
二、题解描述

三、题解代码：

class Solution {
    public int countPrimes(int n) {
        if(n<=2){
            return 0;
        }
        Boolean isPrimes[] = new Boolean[n];
        for(int i=0; i<n; i++){
            isPrimes[i] = true;
        }
        //埃氏筛选算法主体
        for(int i=2 ; i<n ; i++){
            if(isPrimes[i]){
                int k=3;
                for(int j=i*2; j<n;){
                    isPrimes[j]=false;
                    j=i*k;
                    k++;
                }
            }
        }
        int count=0;
        for(int i=2; i<n ; i++){
            if(isPrimes[i]){
                count++;
            }
        }
        return count;
    }
}