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

• ``````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;
}``````

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

• 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.

• This post is deleted!

• Best code ever seen!!!

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

• 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.

• 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.

• @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:

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.

``````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
*
* 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;
}
}
``````

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

• what is the time complexity?

• @GrubenM what is the time complexity of your solution ?

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