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

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(开发者_如何学C)) {
 
            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 ");
        }
    }
}

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.

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.

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.

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

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

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

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.

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.

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)

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

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.

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

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

}

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