# My Java 256ms solution, can it be faster?

• ``````public class Solution {
public int countPrimes(int n) {
boolean bool[] = new boolean[n];
int counter = 0;
int j = 0;

for (int i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
j = i + i;
if (!bool[i]) {
while (j < n) {

if (!bool[j])   bool[j] = true;
j = j + i;
}
}
}

for (int i = 2; i < bool.length; i++) {
if (!bool[i]) {
counter++;
}

}

return counter;

}
``````

}

• Little better

``````public class Solution {
public int countPrimes(int n) {
boolean bool[] = new boolean[n];
if (n <= 2) return 0;
int counter = n-2;
int j = 0;

for (int i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
j = i + i;
if (!bool[i]) {
while (j < n) {

if (!bool[j]) {
bool[j] = true;
counter --;
}
j = j + i;
}
}
}

return counter;

}
``````

}

• Logic is clear, but how to prove that all composite numbers less than n^2 could be represented by the product of multiple prime numbers less than or equal to n.

• what's the logic or algorithm over here.

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