LeetCode - Algorithms - 204. Count Primes

虽然Difficulty标为Easy，但对自己来说不算简单呀，犯了各种错误。

参考网上的各种代码，才终于跑通了。 算法其实就是经典的 Sieve of Eratosthenes，复杂度 O(NloglogN)

ref

Java

1

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

Submission Detail

  • 20 / 20 test cases passed.
  • Your runtime beats 42.53 % of java submissions.

2

这道题好像可以拿来作为范例学习Java 8 Streams：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.BitSet;
import java.util.IntSummaryStatistics;
import java.util.stream.IntStream;

class Solution {
    public int countPrimes(int n) {
    	final BitSet sieve = new BitSet(n);
    	final IntSummaryStatistics stats = IntStream.rangeClosed(2, n-1)
    	                  .filter(x -> !sieve.get(x))
    	                  .peek(x -> {
    	                      if (x*x < n)
    	                        for(int i = x; i < n; i+=x)
    	                           sieve.set(i);
    	                   })
    	                  .summaryStatistics();
    	return new Long(stats.getCount()).intValue();        
    }
}

Submission Detail

  • 20 / 20 test cases passed.
  • Your runtime beats 14.45 % of java submissions.

代码更精炼了，但性能变差了

3 bottom-up approach

solution of Leetcode 204. Count Primes

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

Submission Detail

  • 20 / 20 test cases passed.
  • Runtime: 13 ms, faster than 77.25% of Java online submissions for Count Primes.
  • Memory Usage: 38.3 MB, less than 5.66% of Java online submissions for Count Primes.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
	if (n<=2) return 0;
	var sqrt = Math.floor(Math.sqrt(n));
	var b = new Array(n);
	b[0]=false;
	b[1]=false;
	for(var i=2;i<n;i++) b[i]=true;
	for(var i=2;i<=sqrt;i++) {
		if (b[i]) {
			for(var j=i*i;j<n;j+=i) {
				b[j]=false;
			}		
		}
	}
	var x=0;
	for(var i=0;i<n;i++) {
		if (b[i]) x++;
	}
	return x;    
};

Submission Detail

  • 20 / 20 test cases passed.
  • Your runtime beats 97.46 % of javascript submissions.