Description:
Count the number of prime numbers less than a non-negative number, n.
本题不知道为什么,不可以使用hashtable来做,如果用了就超时了,只能用数组来存储,代码如下:
1 public class Solution { 2 public int countPrimes(int n) { 3 boolean[] num = new boolean[n]; 4 int count=0; 5 for(int i=2;i<n;i++){ 6 if(!num[i]){ 7 count++; 8 } 9 for(int j=2;j*i<n;j++){ 10 num[i*j]=true; 11 } 12 } 13 return count; 14 } 15 }