1 package countPrimes204; 2 /* 3  * Description: 4  * Count the number of prime numbers less than a non-negative number, n. 5  */ 6 public class Solution { 7     //Time Limit Exceeded 8     /* 9     public static int countPrimes(int n) {10         int number=0;11         for (int i=0;i<n;i++)12             if(IsPrime(i)==true)13                 number++;14         return number;15     }16      public static boolean IsPrime(int n){17            if (n <= 3) 18                 return n > 1;19            else if (n%2==0||n%3==0)20                return false;21            else{22                for(int i=2;i<=Math.sqrt(n);i++){23                    if(n%i == 0)24                        return false;25                }26            }27            return true;28        }29       */30     31     public static int countPrimes(int n) {32         //boolean default is false33         boolean[] IsPrime=new boolean[n];34         int numPrime=0;35         for (int i=2;i<n;i++){36             if (IsPrime[i-1]==false){37                 numPrime++;38                 for(int j=2;i*j<n;j++)39                     IsPrime[i*j-1]=true;40             }41         }42         return numPrime;43     }44     public static void main(String[] args) {45         // TODO Auto-generated method stub46         System.out.println(countPrimes(15000000));47         boolean[] IsPrime=new boolean[2];48         System.out.println(IsPrime[0]);49     }50     //reference51     public int countPrimes2(int n) {52         boolean[] notPrime = new boolean[n];53         int count = 0;54         for (int i = 2; i < n; i++) {55             if (notPrime[i] == false) {56                 count++;57                 for (int j = 2; i*j < n; j++) {58                     notPrime[i*j] = true;59                 }60             }61         }62         return count;63     }64 }