leetcode 204. Count Primes

Seawolf

1. Count the number of prime numbers less than a non-negative number, n.
   
2. 
   
3. Example:
   
4. 
   
5. Input: 10
   
6. Output: 4
   
7. Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

复制代码

1. class Solution {
   
2.     public int countPrimes(int n) {
   
3.         if(n <= 1) return 0;
   
4.         
   
5.         boolean[] arr = new boolean[n];
   
6.         arr[0] = true;
   
7.         arr[1] = true;
   
8.         
   
9.         for(int i = 2; i < Math.sqrt(n) ; i++){
   
10.             if(arr[i] == false){
    
11.                
    
12.                 for(int j = 2 ; j*i < n; j++){
    
13.                
    
14.                     arr[i*j] = true;
    
15.                 }
    
16.             }
    
17.             
    
18.         }
    
19.         int count = 0;
    
20.         
    
21.         for(int i = 2; i< arr.length; i++){
    
22.             
    
23.             if(!arr[i]) count++;
    
24.         }
    
25.         
    
26.         return count;
    
27.     }
    
28.    
    
29. }

复制代码