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;
}
12 ms Java solution modified from the hint method, beats 99.95%


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

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:
 It inverts the
true
/false
meanings in the traditional Sieve of Eratosthenes implementation.
true
, here, means a composite number, not a prime.  It doesn't update the array values for any even numbers.
They all stayfalse
, because changing them totrue
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 nonnegative number, n * @param n a nonnegative 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 forsure notprime 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 primecandidate 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; } }
 It inverts the

@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 } }```
