Don't use static variables without any good reason. count will live in memory until the application runs and will be effected by every invocation of countPrimes() with argument n greater than 3. Even if Leetcode creates a new instance of the Solution for every test (can't check it because I'm not registered there), static variable would maintain the previously assigned value because it doesn't belong to any instances of Solution, but shared among them all.
You will definitely not encounter this issue (but potentially there could be others related to performance) if variable count would be local - i.e. declared inside the countPrimes().
Condition if (n == 0 || n == 1 || n == 2) can be simplified to if (n <= 2). And there's no need to use else clause because you are returning if condition matches.
Similarly, there's no need for the else clause in the nested loop after the break.
So your code can be written like this:
public int countPrimes(int n) {
if (n <= 2) {
return 0;
}
int count = 1;
for (int i = 3; i < n; i++) {
for (int j = 2; j < i; j++) {
if (i % j == 0) break;
if (j == i - 1 && i % j != 0) {
count++;
}
}
}
return count;
}
There are several enhancements we can make to improve performance.
Not every Number is Prime - reducing the number of iterations
As obvious, not every number is prime. The most simple observation we can make is that 2 is the only even number among primes. And if the candidate number is greater than 2 we can skip all even numbers by incrementing the index of the loop by 2.
The next interesting property of primes that we can make use of is that there's no gap between the two first primes - the next prime after 2 is 3. Which means if the candidate number is greater than 3 we don't need to check numbers that are divisible by 2 and by 3.
I.e. we can omit 4 of every 6 consecutive numbers, in other words the candidate number can be represented as N * 6 - 1 and N * 6 + 1, these pair of number will not be divisible neither by 2, no by 3.
To achieve that, we can initialize the loop variable to 6 - int i = 6 and increment it at each iteration step by 6 - i += 6, and at every step of iteration (which would represent the next range of 6 number) we need to check the candidate number against two values: i - 1 and i + 1.
Another improvement we can make is connected with condition j < i. For a large input value n this condition will cause a lot of fruitless iterations because there would be no prime divisors for any given number i greater than sqrt(i) see.
And solution will be more readable if we split the method into two logical parts based on responsibilities: a method that is responsible for checking whether a candidate number is prime, and a method that tracks the number of discovered primes.
public int countPrimes(int n) {
if (n < 3) return 0;
if (n == 3) return 1;
if (n == 4) return 2;
int count = 2;
for (int i = 6; i <= n + n % 6; i += 6) {
if ((i - 1) < n && isPrime(i - 1)) {
count++;
}
if ((i + 1) < n && isPrime(i + 1)) {
count++;
}
}
return count;
}
public boolean isPrime(int candidate) {
if (candidate % 2 == 0 || candidate % 3 == 0) return false;
if (candidate == 5) return true;
if (candidate % 5 == 0) return false;
boolean isPrime = true;
double sqrt = Math.sqrt(candidate);
for (int i = 6; i <= sqrt; i += 6) {
if (candidate % (i - 1) == 0 || candidate % (i + 1) == 0) {
isPrime = false;
break;
}
}
return isPrime;
}
This solution will be faster than the initial version, but we can do better.
Don't recalculate the same Primes
There's no need to recalculate the same prime numbers over and over while checking a candidate number.
Instead, we can store every discovered prime number into a list and then check every candidate number against the previously encountered primes from the list.
public int countPrimes(int n) {
if (n < 3) return 0;
if (n == 3) return 1;
if (n == 4) return 2;
List<Integer> primes = new ArrayList<>();
Collections.addAll(primes, 2, 3); // this line will be executed only if n > 4, hence we need to add primes 2 and 3 into the list
// we don't need variable `count` anymore, instead we can check the size of primes
for (int i = 6; i <= n + n % 6; i += 6) {
if (i - 1 < n && isPrime(i - 1, primes)) {
primes.add(i - 1);
}
if (i + 1 < n && isPrime(i + 1, primes)) {
primes.add(i + 1);
}
}
return primes.size();
}
public boolean isPrime(int candidate, List<Integer> primes) {
boolean isPrime = true;
double sqrt = Math.sqrt(candidate);
for (int i = 0; i < primes.size() && primes.get(i) < sqrt; i++) {
if (candidate % primes.get(i) == 0) {
isPrime = false;
break;
}
}
return isPrime;
}
