I'm getting desired output, but I'm not able to submit the code on the Leetcode.
The link of question on the Leetcode
Problem statement:
Given an integer
n, return the number of prime numbers that are strictly less thann.
Constraints:
0 <= n <= 5 * 10 ^ 6
My code:
class Solution {
public static int count = 1;
public int countPrimes(int n) {
if (n == 0 || n == 1 || n == 2)
return 0;
else
for (int i = 3; i < n; i ) {
for (int j = 2; j < i; j ) {
if (i % j == 0) {
break;
} else if (j == i - 1 && i % j != 0) {
count ;
}
}
}
return count;
}
}
It gives the desired result all the time but when I try to submit it, it shows that only 4/66 tests cases are passed.
Can someone please tell me what's wrong here and why I'm not able to submit the solution?
CodePudding user response：
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 cause a lot of fruitless iterations because there would be no prime devisors 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;
}
CodePudding user response：
Use "Sieve of Eratosthenes" algorithm
Your solution is checking each number in the range if it is prime or not. For each number it is finding a divisor of the number from 2 to the number. That's why it is taking more time. In Leetcode your solution should be run within given time limit. You could skip even numbers. It is also useful to note that If a number is prime you can skip checking all its multiples.
Use "Sieve of Eratosthenes" algorithm.