算法面试题之统计N以内素数的个数

主要有两种方法：

一种是按照素数的定义来逐个进行判断。

一种是通过埃筛法（素数的相关特性）对素数进行标识筛选。

/**
 * 统计N以内素数的个数
 */
public class PrimeNumberStatTest {

    public static void main(String[] args) {
        System.out.println(byDefine(100));

        System.out.println(byEthmoidalMethod(100));
    }

    /**
     * 按照素数的定义来实现统计： 素数只能被1和它本身整除，不包含0、1
     * @param n
     * @return 返回素数个数
     */
    public static int byDefine(int n){
        int count = 0;
        for(int i=2;i<n;i++){
            if(isPrime(i)){
                count++;
            }
        }
        return count;
    }

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

    /**
     * 通过埃筛法进行统计：通过素数的特性来进行标识，如果一个数a为素数，那么a的2、3......n-1倍数必然不是素数
     * @return
     */
    public static int byEthmoidalMethod(int n){
        boolean[] primeFlags = new boolean[n]; // false表示素数
        int count = 0;
        for(int i=2;i<n;i++){
            if(!primeFlags[i]){
                count++;
                for(int j=i*i;j<n;j+=i){
                    primeFlags[j] = true;
                }
            }
        }
        return count;
    }

}