`

Leetcode - Count Primes

    博客分类:
  • Math
 
阅读更多
[ref]
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://leetcode.com/discuss/34622/my-c-solutions-in-44ms-time-nearly-o-n-and-space-nearly-o-n

public class Solution {
    // https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    // https://leetcode.com/discuss/34622/my-c-solutions-in-44ms-time-nearly-o-n-and-space-nearly-o-n
    public int countPrimes(int n) {
        if (n < 3) return 0;
        int sqrtN = (int)Math.sqrt(n); // trick 0: use sqrt
        int counter = n / 2; //trick 1: all even num except 2 is not prime 
        boolean[] prime = new boolean[n];
        for (int i = 1; i < n; i += 2)
            prime[i] = true;
        for (int i = 3; i <= sqrtN; i += 2) { // trick 2: skip even num
            if (prime[i]) {
                // mark multiples of i not prime
                for (int j = i * i; j < n; j += i) { // trick 3: start from i*i
                    if (prime[j]) {
                        prime[j] = false;
                        counter--; // trick 4: avoid another loop
                    }
                }
            }
        }
        return counter;
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics