# Concise JAVA solution with explanation

• Special thanks for StefanPochmann's precious advices!

The basic idea is:

``````Once we find a prime number i, then mark the composite numbers:

i*i, i*i+i, i*i+i*2 .. i*i+i*k < n
``````

Hints:

``````1) 1 is not a prime number
2) n is excluded
3) As (i-1)*i is already marked in the previous case of i-1, so we can start from i*i
``````

Time complexity = O(n) + O(overlapped possibilities) - Detailed Analysis

There're overlapped possibilities: 24=2x12, 3x8, 4x6..so it should be more than O(n). The time complexity is: O(n) + O(overlapped possibilities)

``````public int countPrimes(int n) {
boolean isComposite[] = new boolean[n];// isComposite[i]: If i is a composite number
int count = 0;
for (int i = 2; i < n; i++) {
if (!isComposite[i]) {
count++;
if (i < Math.sqrt(n))
for (int j = i * i; j < n; j += i)
isComposite[j] = true;// Mark j as a composite number
}
}
return count;
}
``````

• That's not O(n).

• StefanPochmann, thanks for the comment, not very sure about the time complexity. Is it O(n)(outer loop)+O(n)(inner loop) = O(2n) = O(n)?

• Oh, got it, there're overlapped possibilities: 24=2x12, 3x8, 4x6..so it should be more than O(n). The time complexity is: O(n) + O(overlapped possibilities )

• The loops are nested, you can't just add their complexities.

Let's do an experiment: Count how often `isComposite[j] = true;` gets executed. How often does it get executed for n being 10, 100, 1000, 10000, and 100000?

• Yep, so it should be O(n) + O(overlapped possibilities ), if write like this, it will be executed n times at most. But we still have to use O(n) + O(overlapped possibilities ) to check if (!isComposite[j] ):

``````for (int j = i; j < n; j += i)
if (!isComposite[j] )// <--
isComposite[j] = true;// Mark j as a composite number``````

• Haha, yeah, that check doesn't really help :-)

There's some analysis here, though that's for an improved version (starting `j` at `i` is wasteful).

• Awesome! It helps a lot, appreciate it, bro.

• I see you start j at i*2 now. That's better, but you can start it even later...

• We can start from i*i, LOL, thanks for your smart comment!

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