title: What would be the fastest method to test for primality in Java?
body: <p>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)?</p>
  <pre><code>public class Prime {
      public static boolean isPrime1(int n) {
          if (n &lt;= 1) {
              return false;
          }
          if (n == 2) {
              return true;
          }
          for (int i = 2; i &lt;= Math.sqrt(n) + 1; i++) {
              if (n % i == 0) {
                  return false;
              }
          }
          return true;
      }
      public static boolean isPrime2(int n) {
          if (n &lt;= 1) {
              return false;
          }
          if (n == 2) {
              return true;
          }
          if (n % 2 == 0) {
              return false;
          }
          for (int i = 3; i &lt;= 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&lt;Long, String&gt; methodMap = new TreeMap&lt;Long, String&gt;();
   
          for (Method method : Prime.class.getDeclaredMethods()) {
   
              long startTime = System.currentTimeMillis();
   
              int primeCount = 0;
              for (int i = 0; i &lt; 1000000; i++) {
                  if ((Boolean) method.invoke(prime, i)) {
                      primeCount++;
                  }
              }
   
              long endTime = System.currentTimeMillis();
   
              Assert.assertEquals(method.getName() + &quot; failed &quot;, 78498, primeCount);
              methodMap.put(endTime - startTime, method.getName());
          }
   
   
          for (Entry&lt;Long, String&gt; entry : methodMap.entrySet()) {
              System.out.println(entry.getValue() + &quot; &quot; + entry.getKey() + &quot; Milli seconds &quot;);
          }
      }
  }
  </code></pre>