I am trying to find the fastest way to check whether a given number is prime or not (in Java). Below are several primality testing methods I came up with. Is there any better way than the second implementation(isPrime2)?

    public class Prime {

        public static boolean isPrime1(int n) {
            if (n <= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
        public static boolean isPrime2(int n) {
            if (n <= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            if (n % 2 == 0) {
                return false;
            }
            for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }



public class PrimeTest {

    public PrimeTest() {
    }

    @Test
    public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {

        Prime prime = new Prime();
        TreeMap<Long, String> methodMap = new TreeMap<Long, String>();


        for (Method method : Prime.class.getDeclaredMethods()) {

            long startTime = System.currentTimeMillis();

            int primeCount = 0;
            for (int i = 0; i < 1000000; i++) {
                if ((Boolean) method.invoke(prime, i)) {
                    primeCount++;
                }
            }

            long endTime = System.currentTimeMillis();

            Assert.assertEquals(method.getName() + " failed ", 78498, primeCount);
            methodMap.put(endTime - startTime, method.getName());
        }


        for (Entry<Long, String> entry : methodMap.entrySet()) {
            System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds ");
        }
    }
}
  • 1
    If you need to know that the number is 100% prime, your solution is the best. – Aurril Mar 5 '10 at 10:14
  • I think your solution will do fine. You might hash the results so you only need to 'calculate' it once. Why do you use reflection for executing a test btw? – Stefan Hendriks Mar 5 '10 at 10:29
  • @Stefan Hendriks add a method to the class , fire the test and you will get the sorted result ( i am very lazy). – Anantha Kumaran Mar 5 '10 at 10:44
  • 1
    JUnit @Test annotation FTW ;) – basszero Mar 5 '10 at 11:52
  • 1
    @SimonT: The problem is that a/4 is not the same as a>>2 because of the negative numbers rounding up instead of down. Unless the compiler can prove a>=0, it has to generate a rather complicated expression in order to avoid the division (still an improvement, but something like 3 cycles instead of a single instruction). – maaartinus Nov 25 '13 at 14:52

13 Answers 13

up vote 67 down vote accepted

Here's another way:

boolean isPrime(long n) {
    if(n < 2) return false;
    if(n == 2 || n == 3) return true;
    if(n%2 == 0 || n%3 == 0) return false;
    long sqrtN = (long)Math.sqrt(n)+1;
    for(long i = 6L; i <= sqrtN; i += 6) {
        if(n%(i-1) == 0 || n%(i+1) == 0) return false;
    }
    return true;
}

and BigInteger's isProbablePrime(...) is valid for all 32 bit int's.

EDIT

Note that isProbablePrime(certainty) does not always produce the correct answer. When the certainty is on the low side, it produces false positives, as @dimo414 mentioned in the comments.

Unfortunately, I could not find the source that claimed isProbablePrime(certainty) is valid for all (32-bit) int's (given enough certainty!).

So I performed a couple of tests. I created a BitSet of size Integer.MAX_VALUE/2 representing all uneven numbers and used a prime sieve to find all primes in the range 1..Integer.MAX_VALUE. I then looped from i=1..Integer.MAX_VALUE to test that every new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i).

For certainty 5 and 10, isProbablePrime(...) produced false positives along the line. But with isProbablePrime(15), no test failed.

Here's my test rig:

import java.math.BigInteger;
import java.util.BitSet;

public class Main {

    static BitSet primes;

    static boolean isPrime(int p) {
        return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
    }

    static void generatePrimesUpTo(int n) {
        primes = new BitSet(n/2);

        for(int i = 0; i < primes.size(); i++) {
            primes.set(i, true);
        }

        primes.set(0, false);
        int stop = (int)Math.sqrt(n) + 1;
        int percentageDone = 0, previousPercentageDone = 0;
        System.out.println("generating primes...");
        long start = System.currentTimeMillis();

        for(int i = 0; i <= stop; i++) {
            previousPercentageDone = percentageDone;
            percentageDone = (int)((i + 1.0) / (stop / 100.0));

            if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
                System.out.println(percentageDone + "%");
            }

            if(primes.get(i)) {
                int number = (i * 2) + 1;

                for(int p = number * 2; p < n; p += number) {
                    if(p < 0) break; // overflow
                    if(p%2 == 0) continue;
                    primes.set(p/2, false);
                }
            }
        }
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
    }

    private static void test(final int certainty, final int n) {
        int percentageDone = 0, previousPercentageDone = 0;
        long start = System.currentTimeMillis();
        System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
        for(int i = 1; i < n; i++) {
            previousPercentageDone = percentageDone;
            percentageDone = (int)((i + 1.0) / (n / 100.0));
            if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
                System.out.println(percentageDone + "%");
            }
            BigInteger bigInt = new BigInteger(String.valueOf(i));
            boolean bigIntSays = bigInt.isProbablePrime(certainty);
            if(isPrime(i) != bigIntSays) {
                System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
                    + bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
                    " a prime");
                return;
            }
        }
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
                " minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
    }

    public static void main(String[] args) {
        int certainty = Integer.parseInt(args[0]);
        int n = Integer.MAX_VALUE;
        generatePrimesUpTo(n);
        test(certainty, n);
    }
}

which I ran by doing:

java -Xmx1024m -cp . Main 15

The generating of the primes took ~30 sec on my machine. And the actual test of all i in 1..Integer.MAX_VALUE took around 2 hours and 15 minutes.

  • isPrime3 failed expected:<78498> but was:<78618> – Anantha Kumaran Mar 5 '10 at 10:39
  • (long)Math.sqrt(n) should've been (long)Math.sqrt(n)+1 – Bart Kiers Mar 5 '10 at 10:58
  • isPrime3 2213 Milli seconds isPrime2 3039 Milli seconds isPrime1 6030 Milli seconds you beat me – Anantha Kumaran Mar 5 '10 at 11:01
  • 2
    Do you have a source or evidence for what you say about BigInteger? What certainty are you using? I have seen isProbablePrime(1) fail with the number 9, so the implication in your answer that it is /always/ valid is obviously wrong, but at what certainty can you trust that an int /is prime/? How about long? – dimo414 Oct 29 '10 at 9:04
  • 3
    As this is the first result for java isprime search, I think it is important to highlight a flaw in this answer. For every certainty, one could get a wrong answer. This is because isProbablePrime uses a Random instance to select witnesses (and based on the length of the number, even overrides the certainty). Example: ideone.com/t3lo9G – tb- Mar 30 '13 at 12:01

This is the most elegant way:

public static boolean isPrime(int n) {
    return !new String(new char[n]).matches(".?|(..+?)\\1+");
}

Java 1.4+. No imports needed.

So short. So beautiful.

  • 8
    why does this work? – bgroenks Jun 7 '12 at 4:43
  • 4
    This regex basically does a trial division of a number in unary. It has been mentioned in Perl many times; you can see it explained on many sites e.g. stackoverflow.com/questions/3329766 noulakaz.net/weblog/2007/03/18/… The only difference in Java is 1) .matches() matches the entire string, so you don't need ^ and $, and 2) instead of repeating 1s (which is hard in Java), I create a string of all null characters (by creating a string with a new char array), and then match them with . – user102008 Jun 7 '12 at 8:20
  • 28
    If "elegant" means "clever and concise," then certainly. If "elegant" means "readable," I'd say not. I certainly wouldn't want to run across this in code. – Paul Cantrell Feb 19 '13 at 0:05
  • 15
    @anula tens of thousands of times slower than the simplest algorithms – Esailija May 14 '13 at 9:25
  • 15
    There is nothing elegant about this. – wvdz Apr 23 '14 at 18:15

Take a look at the AKS primality test (and its various optimizations). It is a deterministic primality test that runs in polynomial time.

There is an implementation of the algorithm in Java from the University of Tuebingen (Germany) here

  • 5
    Wikipedia: "While the algorithm is of immense theoretical importance, it is not used in practice. For 64-bit inputs, the Baillie–PSW is deterministic and runs many orders of magnitude faster. For larger inputs, the performance of the (also unconditionally correct) ECPP and APR tests is far superior to AKS." That's the practical consequence of omitting the multiplication constants in the definition of O(n). – Honza Zidek Jun 1 '15 at 8:45
  • 1
    Even the linked implementation says "Therefor, the AkS test is only of interest with respect to computational complexity theory. Testing 2^13-1 needs roughly 30 min with an efficient implementation." 30 minutes to test the number 8191. That's some seriously slow testing. There are much faster versions of AKS, but it's still not a good answer to this question. – DanaJ Apr 25 '17 at 0:10
  • 1
    The implementation link is apparently dead again, although still around in archive.org: web.archive.org/web/20150717104434/http://… – l'L'l Mar 12 at 8:20

You took the first step in eliminating all multiples of 2.

However, why did you stop there? you could have eliminated all multiples of 3 except for 3, all multiples of 5 except for 5, etc.

When you follow this reasoning to its conclusion, you get the Sieve of Eratosthenes.

  • multiples of 3 and 5 and will get elliminated in the first two iteration of the for loop. Sieve of Eratosthenes method is particularly good for generating a series of primes(IMHO) – Anantha Kumaran Mar 5 '10 at 10:21
  • 2
    You don't mean powers, you mean multiples. – principal-ideal-domain May 30 '15 at 8:59

If you are just trying to find if a number is prime or not it's good enough, but if you're trying to find all primes from 0 to n a better option will be the Sieve of Eratosthenes

But it will depend on limitations of java on array sizes etc.

Your algorithm will work well for reasonably small numbers. For big numbers, advanced algorithms should be used (based for example on elliptic curves). Another idea will be to use some "pseuso-primes" test. These will test quickly that a number is a prime, but they aren't 100% accurate. However, they can help you rule out some numbers quicker than with your algorithm.

Finally, although the compiler will probably optimise this for you, you should write:

int max =  (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}

What you have written is what most common programmers do and which should be sufficient most of the time.

However, if you are after the "best scientific algorithm" there are many variations (with varying levels of certainty) documented http://en.wikipedia.org/wiki/Prime_number.

For example, if you have a 70 digit number JVM's physical limitations can prevent your code from running in which case you can use "Sieves" etc.

Again, like I said if this was a programming question or a general question of usage in software your code should be perfect :)

Dependent on the length of the number you need to test you could precompute a list of prime numbers for small values (n < 10^6), which is used first, if the asked number is within this range. This is of course the fastest way. Like mentioned in other answers the Sieve of Eratosthenes is the preferred method to generate such a precomputed list.

If your numbers are larger than this, you can use the primality test of Rabin. Rabin primality test

i think this method is best. at least for me-

    public static boolean isPrime(int num)
    {
        for (int i = 2; i<= num/i; i++)
        {
            if (num % i == 0)
            {
                return false;
            }
        }
        return num > 1;
    }

A fast test due to Jaeschke (1993) is a deterministic version of the Miller-Rabin test, which has no false positives below 4,759,123,141 and hence can be applied to Java ints.

// Given a positive number n, find the largest number m such
// that 2^m divides n.
private static int val2(int n) {
  int m = 0;
  if ((n&0xffff) == 0) {
    n >>= 16;
    m += 16;
  }
  if ((n&0xff) == 0) {
    n >>= 8;
    m += 8;
  }
  if ((n&0xf) == 0) {
    n >>= 4;
    m += 4;
  }
  if ((n&0x3) == 0) {
    n >>= 2;
    m += 2;
  }
  if (n > 1) {
    m++
  }
  return m;
}

// For convenience, handle modular exponentiation via BigInteger.
private static int modPow(int base, int exponent, int m) {
  BigInteger bigB = BigInteger.valueOf(base);
  BigInteger bigE = BigInteger.valueOf(exponent);
  BigInteger bigM = BigInteger.valueOf(m);
  BigInteger bigR = bigB.modPow(bigE, bigM);
  return bigR.intValue();
}

// Basic implementation.
private static boolean isStrongProbablePrime(int n, int base) {
  int s = val2(n-1);
  int d = modPow(b, n>>s, n);
  if (d == 1) {
    return true;
  }
  for (int i=1; i < s; i++) {
    if (d+1 == n) {
      return true;
    }
    d = d*d % n;
  }
  return d+1 == n;
}

public static boolean isPrime(int n) {
  if ((n&1) == 0) {
    return n == 2;
  }
  if (n < 9) {
    return n > 1;
  }

  return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61);
}

This doesn't work for long variables, but a different test does: the BPSW test has no counterexamples up to 2^64. This basically consists of a 2-strong probable prime test like above followed by a strong Lucas test which is a bit more complicated but not fundamentally different.

Both of these tests are vastly faster than any kind of trial division.

There are of course hundreds of primality tests, all with various advantages and disadvantages based on size of number, special forms, factor size, etc.

However, in java I find the most useful one to be this:

BigInteger.valueOf(long/int num).isProbablePrime(int certainty);

Its already implemented, and is quite fast (I find it takes ~6 seconds for a 1000x1000 matrix filled with longs 0–2^64 and a certainty of 15) and probably better optimized than anything we mortals could come up with.

It uses a version of the Baillie–PSW primality test, which has no know counterexamples. (though it might use a slightly weaker version of the test, which may err sometimes. maybe)

I optimized the trial division here: it returns a Boolean. The methods other than isPrime(n) are also needed.

    static boolean[] smlprime = {false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false};

public static boolean isPrime(long n) { //optimised
    if (n < 2) {
        return false;
    }
    if (n < smlprime.length) //less than smlprime.length do not need to be checked
    {
        return smlprime[(int) n]; //lol already checked
    }

    long[] dgt = longDigits(n);
    long ones = dgt[dgt.length - 1];
    if (ones % 2 == 0) {
        return false;
    }
    if (ones == 0 || ones == 5) {
        return false;
    }
    if (digitadd(n) % 3 == 0) {
        return false;
    }
    if (n % 7 == 0) {
        return false;
    }
    if (Square(n)) {
        return false;
    }
    long hf = (long) Math.sqrt(n);
    for (long j = 11; j < hf; j = nextProbablePrime(j)) {
        //System.out.prlongln(Math.sqrt(i));
        if (n % j == 0) {
            return false;
        }
        //System.out.prlongln("res"+res);
    }
    return true;
}

public static long nextProbablePrime(long n) {
    for (long i = n;; i++) {
        if (i % 2 != 0 && i % 3 != 0 && i % 7 != 0) {
            return i;
        }
    }
}

public static boolean Square(long n) {
    long root = (long) Math.sqrt(n);
    return root * root == n;
}

public static long[] longDigits(long n) {
    String[] a = Long.toString(n).split("(?!^)");
    long[] out = new long[a.length];
    for (int i = 0; i < a.length; i++) {
        out[i] = Long.parseLong(a[i]);
    }
    return out;
}

public static long digitadd(long n) {
    long[] dgts = longDigits(n);
    long ans = 0;
    for (long i : dgts) {
        ans += i;
    }
    return ans;
}

Algorithm Efficiency : O( n^(1/2)) Algorithm

Note: This sample code below contains count variables and calls to a print function for the purposes of printing the results :

import java.util.*;

class Primality{
    private static void printStats(int count, int n, boolean isPrime) {

        System.err.println( "Performed " + count + " checks, determined " + n
        + ( (isPrime) ? " is PRIME." : " is NOT PRIME." ) );
    }
    /**
    *   Improved O( n^(1/2)) ) Algorithm
    *    Checks if n is divisible by 2 or any odd number from 3 to sqrt(n).
    *    The only way to improve on this is to check if n is divisible by 
    *   all KNOWN PRIMES from 2 to sqrt(n).
    *
    *   @param n An integer to be checked for primality.
    *   @return true if n is prime, false if n is not prime.
    **/
    public static boolean primeBest(int n){
        int count = 0;
        // check lower boundaries on primality
        if( n == 2 ){ 
            printStats(++count, n, true);
            return true;
        } // 1 is not prime, even numbers > 2 are not prime
        else if( n == 1 || (n & 1) == 0){
            printStats(++count, n, false);
            return false;
        }

        double sqrtN = Math.sqrt(n);
        // Check for primality using odd numbers from 3 to sqrt(n)
        for(int i = 3; i <= sqrtN; i += 2){
            count++;
            // n is not prime if it is evenly divisible by some 'i' in this range
            if( n % i == 0 ){ 
                printStats(++count, n, false);
                return false;
            }
        }
        // n is prime
        printStats(++count, n, true);
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            int n = scan.nextInt();
            primeBest(n);
            System.out.println();
        }
        scan.close();
    }
}

When the prime number 2147483647 is entered, it produces the following output:

Performed 23170 checks, determined 2147483647 is PRIME.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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