# My detailed understandable solution JAVA

• ``````public class Solution {
public int countPrimes(int n) {
if(n<3)
return 0;
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i]=i;
}

arr[0]=-1;
arr[1]=-1;
for(int i=2; i<n; i++){
if(arr[i]!=-1){
int j=2;
while(i*j<n){
arr[i*j]=-1;
j++;
}
}
}
int count=0;
for(int i:arr){
if(i!=-1)
count++;
}
return count;
}
}``````

• Why not use an array of booleans instead of an array of ints? And you can also set "j" to sqrt(i) or start j = i * i as you can see below:

``````// Execution time: 28ms
public class Solution {
public int countPrimes(int n) {
if(n <= 1) return 0;

int sqrt = (int)Math.sqrt(n);
boolean[] primes = new boolean[n];

for(int i = 0; i < n; i++) {
primes[i] = true;
}

primes[0] = false;
primes[1] = false;

for(int i = 2; i <= sqrt; i++) {
if(!primes[i]) continue;

for(int j = i * i; j < n; j += i) {
primes[j] = false;
}
}

int ans = 0;
for(int i = 0; i < n; i++) {
if(primes[i]) {
ans++;
}
}

return ans;
}
}``````

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