LeetCode 204. Count Primes

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解题思路：

埃拉托斯特尼筛法，将2、3、5...的所有质数的倍数都标记为非质数，最后可求。

	public static int countPrimes(int n) {
		int res=0;
		boolean prime[]=new boolean[n];
		for(int i=2;i<n;i++)
		{
			if(!prime[i])
			{
				++res;
				for(int j=2;i*j<n;j++)
					prime[i*j]=true;
			}
		}
		return res;
        
    }