What would be the fastest method to test for primality in Java?

Question

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 ");
        }
    }
}

If you need to know that the number is 100% prime, your solution is the best. — Aurril, Mar 05 '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 05 '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 05 '10 at 10:44
It's not the fastest, it computes repeatedly `Math.sqrt(n)` and I think the compiler can't optimize it away. Using `n&1` instead of`n%2` would be a simple improvement. — maaartinus, Feb 02 '11 at 09:29
@maaartinus I read on the USACO training program's tutorials that: "Some zealous optimizing coders like to change `a/4 to '(a>>2)'` in order to save time... Modern compilers know all about this and perform such substitutions automatically, thus leaving the better programmer to write a/4 when that is what's meant." Just food for thought. — SimonT, Nov 25 '13 at 04:34
@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
The tricks needed to achieve speed usually sacrifices elegancy. — Thorbjørn Ravn Andersen, Mar 05 '10 at 11:36
What do you need this for? How big are your numbers (how many bits)? How many numbers from what range do you need to test? — starblue, Mar 05 '17 at 18:08

Bart Kiers · Accepted Answer · 2010-10-31T08:07:28.937

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 2213 Milli seconds isPrime2 3039 Milli seconds isPrime1 6030 Milli seconds you beat me — Anantha Kumaran, Mar 05 '10 at 11:01
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 09:04
@dimo414, true, I forgot to mention certainty. 25 should be enough, (probably less) but I can't find the reference right now. Will look at this later today. — Bart Kiers, Oct 29 '10 at 09:26
Just use certainty > 32 if you are working with 32 bit integers. — Thomas Ahle, Feb 06 '11 at 14:11
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: http://ideone.com/t3lo9G — tb-, Mar 30 '13 at 12:01
You only need a list of primes up to 16 bits to have 100% certainty dividing any 32bits int by them. — juanmf, Jun 15 '22 at 17:54

user102008 · Answer 2 · 2011-02-24T23:03:09.037

42

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.

edited Feb 24 '11 at 23:03

answered Dec 23 '10 at 03:42

user102008

30,736
10
83
104

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. http://stackoverflow.com/questions/3329766/ http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ The only difference in Java is 1) `.matches()` matches the entire string, so you don't need `^` and `$`, and 2) instead of repeating `1`s (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 07 '12 at 08:20
I guess I haven't worked with really complex regex expressions... so to me it just looks like a bunch of random symbols. What are the '.', '?', and '+' signs doing? I assume '|' is a bitwise OR right? – bgroenks Jun 07 '12 at 16:06
3

@ghostsoldier23: `.` matches any character. `+` matches 1 or more occurrences of the previous thing. `?` could mean 0 or 1 of the previous thing; when used after `*` or `+` it also means "non-greedy" match. And `|` means OR, so either of the left or right. `\1` is a back-reference, i.e. a repetition of what was matched in the first group. Basically, `..+` serves to match 2 or more characters (`..+?` simply makes it non-greedy); and `(thing above)\\1+` serves to match 2 or more repetitions of the thing above, so it comes out to (number 2 or greater) x (number 2 or greater) (non-prime) # of char – user102008 Jun 07 '12 at 19:06
36

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 00:05
21

@anula tens of thousands of times slower than the simplest algorithms – Esailija May 14 '13 at 09:25
1

@PaulCantrell The Carmack's [fastest sqrt root](http://en.wikipedia.org/wiki/Fast_inverse_square_root) function is also unreadable, but is the most fastest. – 4gus71n Jan 25 '14 at 06:05
@anula Not much, I ran this algorithm against the @BartKiers algorithm with a test set of 0 to `Integer.MAX_VALUE` and this one lose. – 4gus71n Jan 25 '14 at 06:32
20

There is nothing elegant about this. – wvdz Apr 23 '14 at 18:15
4

The regex is essentially equivalent to division by the positive integer series, which is the `worst case` `naive` solution to figuring out whether a number is prime or not. – Samveen Nov 23 '14 at 12:40
This is slow, cryptic and definitely not elegant. – lukad Nov 15 '22 at 09:45

score 12 · Answer 3 · edited Jan 26 '16 at 04:18

12

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.

edited Jan 26 '16 at 04:18

Joe

3,370
4
33
56

answered Mar 05 '10 at 10:19

Jimmy

89,068
17
119
137

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 05 '10 at 10:21
2

You don't mean powers, you mean multiples. – principal-ideal-domain May 30 '15 at 08:59

score 12 · Answer 4 · edited May 23 '16 at 14:36

12

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

edited May 23 '16 at 14:36

zx485

28,498
28
50
59

answered Mar 05 '10 at 10:24

Brandon E Taylor

24,881
6
47
71

6

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 01 '15 at 08:45
2

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 00:10
1

The implementation link is apparently dead again, although still around in archive.org: https://web.archive.org/web/20150717104434/http://www-ti.informatik.uni-tuebingen.de:80/~reinhard/krypto/AKSTest/AKSeng.html – l'L'l Mar 12 '18 at 08:20

Ariful Islam · Answer 5 · 2016-11-20T09:10:15.580

7

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;
    }

edited Nov 20 '16 at 09:10

answered Nov 02 '14 at 14:09

Ariful Islam

664
8
12

score 5 · Answer 6 · edited Feb 03 '12 at 00:21

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) {
}

score 5 · Answer 7 · edited Oct 03 '20 at 08:33

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(base, 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.

score 4 · Answer 8 · answered Mar 05 '10 at 10:23

4

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.

answered Mar 05 '10 at 10:23

saugata

2,823
1
27
39

score 4 · Answer 9 · answered Mar 23 '17 at 23:46

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)

score 3 · Answer 10 · answered Mar 05 '10 at 10:20

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 :)

score 3 · Answer 11 · answered Mar 05 '10 at 10:23

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

score 1 · Answer 12 · edited Jul 05 '18 at 20:54

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.

score 0 · Answer 13 · answered Sep 27 '18 at 02:47

tested in a Intel Atom @ 1.60GHz, 2GB RAM, 32-bit Operating System

test result:
largest prime number below Long.MAX_VALUE=9223372036854775807 is 9223372036854775783
elapsed time is 171499 milliseconds or 2 minutes and 51 seconds

public class PrimalityTest
{
    public static void main(String[] args)
    {
        long current_local_time = System.currentTimeMillis();
        long long_number = 9223372036854775783L;
        long long_a;
        long long_b;
        if (long_number < 2)
        {
            System.out.println(long_number + " is not a prime number");
        }
        else if (long_number < 4)
        {
            System.out.println(long_number + " is a prime number");
        }
        else if (long_number % 2 == 0)
        {
            System.out.println(long_number + " is not a prime number and is divisible by 2");
        }
        else
        {
            long_a = (long) (Math.ceil(Math.sqrt(long_number)));
            terminate_loop:
            {
                for (long_b = 3; long_b <= long_a; long_b += 2)
                {
                    if (long_number % long_b == 0)
                    {
                        System.out.println(long_number + " is not a prime number and is divisible by " + long_b);
                        break terminate_loop;
                    }
                }
                System.out.println(long_number + " is a prime number");
            }
        }
        System.out.println("elapsed time: " + (System.currentTimeMillis() - current_local_time) + " millisecond/s");
    }
}

Mohammad · Answer 14 · 2020-07-02T02:58:43.950

First and foremost, primes start from 2. 2 and 3 are primes. Prime should not be dividable by 2 or 3. The rest of the primes are in the form of 6k-1 and 6k+1. Note that you should check the numbers up to SQRT(input). This approach is very efficient. I hope it helps.

public class Prime {

    public static void main(String[] args) {
        System.out.format("%d is prime: %s.\n", 199, isPrime(199)); // Prime
        System.out.format("%d is prime: %s.\n", 198, isPrime(198)); // Not prime
        System.out.format("%d is prime: %s.\n", 104729, isPrime(104729)); // Prime
        System.out.format("%d is prime: %s.\n", 104727, isPrime(982443529)); // Prime
    }

    /**
     * Tells if a number is prime or not.
     *
     * @param input the input
     * @return If the input is prime or not
     */
    private boolean isPrime(long input) {
    if (input <= 1) return false; // Primes start from 2
    if (input <= 3) return true; // 2 and 3 are primes
    if (input % 2 == 0 || input % 3 == 0) return false; // Not prime if dividable by 2 or 3
    // The rest of the primes are in the shape of 6k-1 and 6k+1
    for (long i = 5; i <= Math.sqrt(input); i += 6) if (input % i == 0 || input % (i + 2) == 0) return false;
    return true;
    }

}

score 0 · Answer 15 · answered Aug 07 '20 at 17:25

In general, all primes greater than some Primorial integer C is of the form Ck+i for i < C where i and k are integers and i represents the numbers that are coprime to C

Here is an example with C=30, it should work faster than Bart Kiers answer for C=6 and you can improve it by computing C=210

boolean isPrime(long n) {
    if(n < 2){
        return false;
    }
    if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13 || n == 17 || n == 19 || n == 23 || n == 29){
        return true;
    }
    
    long sqrtN = (long) Math.sqrt(n) + 1;
    int[] mods = {1, 7, 11, 13, 17, 19, 23, 29};
    for (long i = 30L; i <= sqrtN; i += 30) {
        for (int mod : mods) {
            if(n % (i + mod) == 0){
                return false;
            }
        }
    }
    return true;
}

What would be the fastest method to test for primality in Java?

15 Answers15

Linked

Related