当前位置：网站首页>204. Count Primes

204. Count Primes

2022-08-03 16:38:00 【51CTO】

Description:

Count the number of prime numbers less than a non-negative number, n.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

       
       public class Solution {  
       
    public int countPrimes(int n) {      
       
        boolean[] a = new boolean[n];  
       
        for(int i=2; i*i<n; i++) {  
       
            if(!a[i]) {  
       
                for(int j=i; i*j<n; j++) {  
       
                    a[i*j] = true;  
       
                }  
       
            }  
       
        }  
       
        int c=0;  
       
        for(int i=2; i<n; i++) {  
       
            if(a[i] == false) 
       
                ++c;  
       
        }  
       
        return c;  
       
    }  
       
}  
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

       
       /**
       
 * @param {number} n
       
 * @return {number}
       
 */
       
var countPrimes = function(n) {
       
    var arr = new Array(n).fill(true);
       
    for (var i = 0; i < Math.sqrt(n); i++) {
       
        if (i < 2) {
       
            arr[i] = false;
       
        }   
       
        if (arr[i]) {
       
            for (var j = i * i; j < n; j += i) {
       
                arr[j] = false;
       
            }
       
        }
       
    }
       
    return arr.filter(i => i === true).length;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

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

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15740726/5540629

当前位置：网站首页>204. Count Primes

204. Count Primes

边栏推荐

猜你喜欢

随机推荐