12 ms Java solution modified from the hint method, beats 99.95%


  • 40
    D
    publib int countPrimes(int n) {
        if (n < 3)
            return 0;
            
        boolean[] f = new boolean[n];
        //Arrays.fill(f, true); boolean[] are initialed as false by default
        int count = n / 2;
        for (int i = 3; i * i < n; i += 2) {
            if (f[i])
                continue;
            
            for (int j = i * i; j < n; j += 2 * i) {
                if (!f[j]) {
                    --count;
                    f[j] = true;
                }
            }
        }
        return count;
    }

  • 0
    E

    So, can you explain why j += 2 * i here ?


  • 0
    D

    both i and j are odd, then i + j is even which must not be a prime number. Only j (odd) + 2 * i (even) can be an odd number.


  • 0
    This post is deleted!

  • 0
    A

    Best code ever seen!!!


  • 22
    H

    i never understand why people cant leave a paragraph or two explanation to their complex solutions


  • 1
    W

    This solution is a subtle optimization of the solution proposed in the subject,which means firstly filter the number is even.The initialization of count=n/2 is obvious,of course lead to i+=2 and j+=i*2.


  • 0
    S

    this solution is mentioned in the 《the beauty of program》, the bit map method. and in this solution, it have a little bug in "for (int i = 3; i * i < n; i += 2)". it should be "i*i <= n". if not including the situation of "i * i = n", it will lost some answer. such as 499979.


  • 0
    S

    @eidision jump the even number, because only odd number have chance to be prime except 2


  • 21
    G

    This is a really clever solution, and it still scores in the top 1% of Java submissions.

    There are a few realizations that are crucial to understanding its implementation:

    1. It inverts the true / false meanings in the traditional Sieve of Eratosthenes implementation.
      true, here, means a composite number, not a prime.
    2. It doesn't update the array values for any even numbers.
      They all stay false, because changing them to true would be needless bookkeeping.

    Here is my refactor of dojiangv's original post, with comments added:

    public class Solution {
        
        /**
         * Count the number of prime numbers less than a non-negative number, n
         * @param n a non-negative integer
         * @return the number of primes less than n
         */
        public int countPrimes(int n) {
            
            /**
             * if n = 2, the prime 2 is not less than n,
             * so there are no primes less than n
             */
            if (n < 3) return 0;
            
            /** 
             * Start with the assumption that half the numbers below n are
             * prime candidates, since we know that half of them are even,
             * and so _in general_ aren't prime.
             * 
             * An exception to this is 2, which is the only even prime.
             * But also 1 is an odd which isn't prime.
             * These two exceptions (a prime even and a for-sure not-prime odd)
             * cancel each other out for n > 2, so our assumption holds.
             * 
             * We'll decrement count when we find an odd which isn't prime.
             *
             * If n = 3,  c = 1.
             * If n = 5,  c = 2.
             * If n = 10, c = 5.
             */
            int c = n / 2;
            
            /**
             * Java initializes boolean arrays to {false}.
             * In this method, we'll use truth to mark _composite_ numbers.
             * 
             * This is the opposite of most Sieve of Eratosthenes methods,
             * which use truth to mark _prime_ numbers.
             * 
             * We will _NOT_ mark evens as composite, even though they are.
             * This is because `c` is current after each `i` iteration below.
             */
            boolean[] s = new boolean[n];
            
            /**
             * Starting with an odd prime-candidate above 2, increment by two
             * to skip evens (which we know are not prime candidates).
             */
            for (int i = 3; i * i < n; i += 2) {
                if (s[i]) {
                    // c has already been decremented for this composite odd
                    continue;
                }
                
                /** 
                 * For each prime i, iterate through the odd composites
                 * we know we can form from i, and mark them as composite
                 * if not already marked.
                 * 
                 * We know that i * i is composite.
                 * We also know that i * i + i is composite, since they share
                 * a common factor of i.
                 * Thus, we also know that i * i + a*i is composite for all real a,
                 * since they share a common factor of i.
                 * 
                 * Note, though, that i * i + i _must_ be composite for an
                 * independent reason: it must be even.
                 * (all i are odd, thus all i*i are odd,
                 * thus all (odd + odd) are even).
                 * 
                 * Recall that, by initializing c to n/2, we already accounted for
                 * all of the evens less than n being composite, and so marking
                 * i * i + (odd)*i as composite is needless bookkeeping.
                 * 
                 * So, we can skip checking i * i + a*i for all odd a,
                 * and just increment j by even multiples of i,
                 * since all (odd + even) are odd.
                 */
                for (int j = i * i; j < n; j += 2 * i) {
                    if (!s[j]) {
                        c--;
                        s[j] = true;
                        }
                    }
                }
            return c;
        }
    }
    

  • 1
    D

    @GrubenM thank you for posting this. I had a solution that worked util it got to the big #s, but it timed out. I've translated your solution to Swift 3.0

        
        func countPrimes(_ n: Int) -> Int {
            guard n > 2 else { return 0 }
            
            var count: Int = n / 2
            
            var potentialPrimes: [Bool] = Array(repeating: false, count: n)
            
            for i in stride(from: 3, to: n, by: 2) where i * i < n {
                if potentialPrimes[i] {
                    continue
                }
                for j in stride(from: (i * i), to: n, by: (2 * i)) {
                    if (!potentialPrimes[j]) {
                        count -= 1
                        potentialPrimes[j] = true
                    }
                }
            }
            
            return count
        }
    }```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.