Description:
Count the number of prime numbers less than a non-negative number, n.
题目大意：给一个int，返回小于它的质数的数量。
解题思路：打表。
public class Solution { public int countPrimes(int n) { int[] count = new int[n+5]; boolean[] isPrime = new boolean[n+5]; Arrays.fill(isPrime, true); isPrime[0]=false; isPrime[1]=false; for(int i=2;i<=n;i++){ count[i]+=count[i-1]; if(isPrime[i]){ count[i]++; for(int j =i*2;j<=n;j+=i){ isPrime[j]=false; } } } return isPrime[n]?count[n]-1:count[n]; } }
原文：http://www.cnblogs.com/aboutblank/p/4599566.html