5
\$\begingroup\$

I've been doing some programming challenges and problems lately and it seems like many involve primes. I concluded that I would benefit from optimizing how I'm checking for them. Currently I'm using the following method:

private static boolean isPrime(int num) {
    if (num < 1) {
        throw new IllegalArgumentException(
            "Argument must be a positive integer." +
            "\n Argument was: " + num + "."
        );
    }
    if (num <= 3){ return num > 1; }
    if ((num & 1) == 0) { return false; }

    for (int i = 5; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

Sometimes altering longs.

Excluding bitwise hacks that would likely come at the cost of readability is this as good as it gets or is there some enhancement that would raise performance?

\$\endgroup\$
  • 3
    \$\begingroup\$ Note that, as written, your method would report that 9 and 21 are prime, which they are not. You can try it at ideone.com/Jnn6QU. \$\endgroup\$ – AJMansfield Jan 10 '15 at 16:51
  • 1
    \$\begingroup\$ So, I don't know if anyone can relate to this, but for some reason when I pasted it in, the i = 3 seemed redundant, despite my spending the day before creating this method and assuring it worked, seconds after pasting it I thought. "Oh! I accounted for it already, I can start at 5!" The truthiness compelled me. Thanks for pointing this out. \$\endgroup\$ – Legato Jan 10 '15 at 23:27
5
\$\begingroup\$

Checking for prime numbers isn't something ideally done in one particular way. Depending on what you're doing, lots of different techniques make sense.

  • If you're generating all prime numbers up to some fixed value, or some fixed proportion thereof, you'll probably want to use a sieve (Sieve of Eratosthenes being the popular choice).

  • If you're generating lots of prime numbers in a given range, but not so many that a sieve makes sense for the whole thing, you'll probably want to generate all primes up to Math.sqrt(highest_expected_value) and do

    for (int prime : primes) {
        if (num % prime == 0) {
            return false;
        }
    }
    
  • If you're only looking at certain kinds of numbers (eg. \$2^n\$) there are often specialized techniques.

  • If you're only doing this once, a small variation of your code is probably best.

  • If you're doing a few calls but not enough for justifying pregenerating all primes up to Math.sqrt(highest_expected_value), potentially you'll still want to cache the first ~1k primes or so.

Note that I say this as someone who has never touched this kind of stuff; mathematicians are far ahead of any naïve implementations and if you want to take this seriously you'd probably want to look at the literature first.


With respect to the code, here are a few comments.

First, are you sure you want to restrict it to positive integers? You can simply define negative integers to not be primes. No need to throw an error.

I would, however change your

if (num <= 3){ return num > 1; }

to the more explicit

if (num <= 3) {
    return num == 2 || num == 3;
}

We can consider that we're filtering (after AJMansfield's fix)

3

5
7
9  // div. by 3

11
13
15  // div by 3

We can avoid a third of this by not including the highlighted terms. Then, continuing from rolfl's improvement, we get

int limit = (long)Math.sqrt(num);
for (int i = 5; i <= int; i += 6) {
    if (num % i == 0 || num % (i+2) == 0) {
        return false;
    }
}
return true;

You need to explicitly include division by 3 now, btw:

// (num & 1) == num % 2
if ((num & 1) == 0 || num % 3 == 0) {
    return false;
}

This gives noticeable speed improvements. In theory this can be expanded to any number of primes; eventually you converge to my fifth bullet ("If you're doing a few calls") and, eventually, to my second and first. Here's an implementation up to a wheel of length 30 \$\left( 2 \times 3\times 5 \right) \$:

private static boolean isPrime(long num) {
    if (num <= 5) {
        return num == 2 || num == 3 || num == 5;
    }

    if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0) {
        return false;
    }

    long limit = (long)Math.sqrt(num);
    for (long i = 7; i <= limit; i += 30) {
        if (
            num % (i+0)  == 0 ||
            num % (i+4)  == 0 ||
            num % (i+6)  == 0 ||
            num % (i+10) == 0 ||
            num % (i+12) == 0 ||
            num % (i+16) == 0 ||
            num % (i+22) == 0 ||
            num % (i+24) == 0
        ) {
            return false;
        }
    }
    return true;
}
\$\endgroup\$
  • \$\begingroup\$ I was going to add the mathematics tag, but was apprehended by the description which indicated that its use should mean a professional mathematician would find the question interesting. Do you think that this would warrant the additional tag? \$\endgroup\$ – Legato Jan 10 '15 at 16:38
  • 2
    \$\begingroup\$ @Legato I'm pretty sure it's valid; I think the warning is to prevent people adding it just because they have a multiplication in their code. \$\endgroup\$ – Veedrac Jan 10 '15 at 16:40
  • \$\begingroup\$ I read the article on negatives not being primed you linked. Thanks for that! I've adjusted my code. \$\endgroup\$ – Legato Jan 11 '15 at 0:07
8
\$\begingroup\$

Unit Testing

I think you should start writing unit tests to verify whether your code is actually working. There's an old saying "first get it right", and your code reports 9 as prime number.

Here's a sample JUnit 4 test for you.

import org.junit.Test;

import static org.junit.Assert.fail;

public class IsPrimeTest {
    @Test
    public void givenPrimeNumber_whenCallingIsPrime_thenReturnsTrue() {
        assertIsPrime(2, 3, 5, 7, 11, 13, 17, 19, 23, 29);
    }

    @Test
    public void givenNotPrimeNumber_whenCallingIsPrime_thenReturnsFalse() {
        assertNotPrime(1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30);
    }

    private static void assertIsPrime(final int... primeNumbers) {
        for (final int primeNumber : primeNumbers)
            if (!IsPrime.isPrime(primeNumber))
                fail("Expected " + primeNumber + " to be prime.");
    }

    private static void assertNotPrime(final int... notPrimeNumbers) {
        for (final int notPrimeNumber : notPrimeNumbers)
            if (IsPrime.isPrime(notPrimeNumber))
                fail("Expected " + notPrimeNumber + " to be prime.");
    }
}

If your interested in coding exercises, you could actually use a Sieve of Eratosthenes in your Unit Test to test your isPrime() method.

Exception vs. return false

It is not "bogus" to ask whether a negative number is a prime number. The result is not undefined. It's defined that negative numbers are not prime numbers because they're given no thought. So I'd rather return false than throw new IllegalArgumentException().

Throwing an exception makes sense where a result cannot be produced with the given output set, i.e. asking for the square root of -1 when the result type is not complex. Throwing an exception does not make sense when a result can actually be reproduced as member of the result set.

So, I'd rather if (num < 2) return false;.

(Just mentioned points which those many good answers didn't cover yet.)

\$\endgroup\$
8
\$\begingroup\$

When misused, private access can frequently result in reduced opportinutues for code reuse, such as in this case. Self-contained static methods in particular should almost never be private, but rather should be moved into a separate utilities class and marked public.

At the same time, you should add javadoc to the method, to further facilitate code reuse:

/**
 * Tests whether a number is prime or not.
 * @param num The number to test.
 * @returns {@code true} if {@code num} is prime, {@code false} otherwise.
 * @throws IllegalArgumentException if {@code num} is zero or negative.
 */

As for readability, I think that (num & 1) == 0 is perfectly clear, however the previous statement, if (num <= 3) return num > 1;, is a little bit unclear. You should replace it with a simple check for one, if (num == 1) return false; and another if (num <= 3) return true; after it.

Note that if you start the loop at 5, you missclassify 9, 15, and 21, which you can see in this ideone sketch: https://ideone.com/Jnn6QU. They are missed because they are less than 25 but not divisible by two. You should start the loop at 3 in order to catch those numbers.

You may wish to consider using BigInteger.isProbablePrime instead of this method, however, as it is much faster for large values. While a true return from that method does not guarantee that the number is prime, you can tune its certainty to your needs.

\$\endgroup\$
  • \$\begingroup\$ But if you write if (num == 1) return false; and if (num <= 3) return true; you are almost always making 2 comparisons. If you write if (num<=3){ ... } you are making 2 comparisons only in rare cases. It is a small difference, but by principle I would always prefer the second option. \$\endgroup\$ – Florian F Jan 11 '15 at 17:03
6
\$\begingroup\$

Note: AJMansfield (in a comment and in this answer (+1 - nice answer)) has pointed out that the code is buggy. It is, and this answer missed that. The algorithm in your code (and my reproduction here), is wrong.

As AJ says, your for-loop should start at 3, not 5.


If you have to test just one number, and never more than one number, then the solution you propose is not too bad. There are some tweaks available, and they will improve performance, but the algorithm itself is decent.

The code style is inconsistent and non-standard though.

1-liner if-statements are a known code-style contravention, yet you do it in a few places:

if (num <= 3){ return num > 1; }
if ((num & 1) == 0) { return false; }

You may want to argue that you can do this in your own style, but, you are inconsistent with it, and that's even worse than the 1-liner. If you are going to use 1-liners for simple conditions, then do it always (and the following should be a 1-liner too):

    if (num % i == 0) {
        return false;
    }

As for your current implementation's performance, there's only one significant issue I see:

for (int i = 5; i * i <= num; i += 2) {

The above code calculates the \$i^2\$ on each iteration. It would be better to calculate the square-root of num first, and then limit the loop that way:

int limit = (int)Math.sqrt(num);
for (int i = 5; i <= limit; i += 2) {
\$\endgroup\$
  • 2
    \$\begingroup\$ Note that 'performance issue' also hides that it's a correctness issue; your version prevents overflow. \$\endgroup\$ – Veedrac Jan 10 '15 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.