Skip to main content
added 1 character in body
Source Link
K_P
  • 151
  • 3

The sieve is optimal for what you try to do. In your code, the isPrime method is not efficient. An easy optimisation is to start your loop from 2 (1 is redundant) and finish your loop on \$\sqrt{n}\$ (this is well known in number theory). Also there is no need to use a list, simply return false when you detect a non prime in the loop. So the whole thing can take a few lines:

public static boolean isPrime(long ln) {
    long end = (long)Math.sqrt(ln) + 1;
    for (int i = 2; i < end; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

The sieve is optimal for what you try to do. In your code, the isPrime method is not efficient. An easy optimisation is to start your loop from 2 (1 is redundant) and finish your loop on \$\sqrt{n}\$ (this is well known in number theory). Also there is no need to use a list, simply return false when you detect a non prime in the loop. So the whole thing can take a few lines:

public static boolean isPrime(long l) {
    long end = (long)Math.sqrt(l) + 1;
    for (int i = 2; i < end; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

The sieve is optimal for what you try to do. In your code, the isPrime method is not efficient. An easy optimisation is to start your loop from 2 (1 is redundant) and finish your loop on \$\sqrt{n}\$ (this is well known in number theory). Also there is no need to use a list, simply return false when you detect a non prime in the loop. So the whole thing can take a few lines:

public static boolean isPrime(long n) {
    long end = (long)Math.sqrt(n) + 1;
    for (int i = 2; i < end; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}
Source Link
K_P
  • 151
  • 3

The sieve is optimal for what you try to do. In your code, the isPrime method is not efficient. An easy optimisation is to start your loop from 2 (1 is redundant) and finish your loop on \$\sqrt{n}\$ (this is well known in number theory). Also there is no need to use a list, simply return false when you detect a non prime in the loop. So the whole thing can take a few lines:

public static boolean isPrime(long l) {
    long end = (long)Math.sqrt(l) + 1;
    for (int i = 2; i < end; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}