Count the number of prime numbers less than a non-negative number, n.
1.常规思路（计算复杂度为O(n*sqrt(n))）,提交后超时。
public static boolean isPrime(int m){ boolean flag = true; for(int i=2; i<=Math.sqrt(m); i++){ if(m % i == 0){ flag = false; break; } } return flag; } public static int countPrimes(int n) { if(n<=2) return 0; else{ int count = 1; for(int i=3; i<n; i++){ if(isPrime(i)) count++; } return count; } }
2.只是统计小于n的素数的个数，则设置一个boolean型的数组，每次将一个素数的倍数设置为非素数，最后遍历一遍数组即可。
public int countPrimes(int n) { boolean[] a = new boolean[n]; for(int i=2; i*i<n; i++){ if(!a[i]){//如果a[i]是素数 for(int j=2; i*j<n; j++){ a[i*j] = true; } } } int count = 0; for(int i=2; i<n; i++){ if(a[i] == false) { count++; } } return count; }
原文：http://www.cnblogs.com/little-YTMM/p/4511195.html